Français
The partially disjoint paths problem
Post-edited
Authors : Schrijver, Alexander (Author of the conference)
CIRM (Publisher )
05C10 - Planar graphs; geometric and topological aspects of graph theory
05C20 - Directed graphs (digraphs), tournaments
05C25 - Graphs and abstract algebra (groups, rings, fields, etc.)
05C38 - Paths and cycles
68Q25 - Analysis of algorithms and problem complexity
90C27 - Combinatorial optimization
CIRM (Publisher )
Loading the player...
|
| planar graph sources and terminals disjoint paths polynomial-time algorithm VLSI directed graphs free group partially disjoint paths graph group fixed parameter tractable |
Abstract :
The partially disjoint paths problem asks for paths $P_1, \ldots,P_k$ between given pairs of terminals, while certain pairs of paths $P_i$,$P_j$ are required to be disjoint. With the help of combinatorial group theory, we show that, for fixed $k$, this problem can be solved in polynomial time for planar directed graphs. We also discuss related problems. No specific foreknowledge is required.
MSC Codes : 05C10 - Planar graphs; geometric and topological aspects of graph theory
05C20 - Directed graphs (digraphs), tournaments
05C25 - Graphs and abstract algebra (groups, rings, fields, etc.)
05C38 - Paths and cycles
68Q25 - Analysis of algorithms and problem complexity
90C27 - Combinatorial optimization
|
Information on the Video
Film maker : Hennenfent, GuillaumeLanguage : English Available date : 14/09/17 Conference Date : 12/09/17 Subseries : Research talks arXiv category : Combinatorics ; Optimization and Control ; Computer Science Mathematical Area(s) : Combinatorics ; Computer Science ; Control Theory & Optimization Format : MP4 (.mp4) - HD Video Time : 00:54:36 Targeted Audience : Researchers Download : https://videos.cirm-math.fr/2017-09-12_Schrijver.mp4 
|
Information on the Event
Event Title : IX Latin and American algorithms, graphs and optimization symposium (LAGOS 2017) / 9e symposium latino et americain des algorithmes, graphes et de l'optimisation (LAGOS 2017)Event Organizers : Bassino, Frédérique ; Bonomo, Flavia ; Pournin, Lionel ; Valencia-Pabon, Mario ; Vera Lizcano, Juan Carlos Dates : 11/09/17 - 15/09/17 Event Year : 2017 Event URL : http://conferences.cirm-math.fr/1660.html
Citation Data
DOI : 10.24350/CIRM.V.19221703Cite this video as: Schrijver, Alexander (2017). The partially disjoint paths problem. CIRM. Audiovisual resource. doi:10.24350/CIRM.V.19221703 URI : http://dx.doi.org/10.24350/CIRM.V.19221703 |
See Also
- [Multi angle] Combinatorial and algorithmic properties of Robinsonian matrices / Author of the conference Laurent, Monique.
- [Multi angle] Coloring graphs with forbidden induced paths / Author of the conference Chudnovsky, Maria.
- [Multi angle] Random hyperbolic graphs / Author of the conference Kiwi, Marcos.
- [Multi angle] Restricted types of matchings / Author of the conference Rautenbach, Dieter.
Bibliography
