MASCOTTE no longer exists => visit the new project-team
Seminaire MASCOTTEDisjoint directed and undirected paths, cycles and trees in directed graphs
par Joergen Bang-Jensen
| Date : | 06/10/09 | | Time : | 10h30 | | Location : | Lagrange Gris |
We survey results and open problems regarding (edge)-disjoint paths, cycles and trees in (di)graphs and illustrate a connection between the directed and the undirected case by studying linking problems for directed graphs for which only some of the objects (paths, cycles or trees) have to following the orientation of the arcs of the given digraph. We also give a generalization of the well-known complexity result by Fortune, Hopcroft and Wyllie from 1980 characterizing which directed linking problems are NP-complete.
Page des séminaires
| 
