English
The partially disjoint paths problem
Post-edited
Auteurs : Schrijver, Alexander (Auteur de la Conférence)
CIRM (Editeur )
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 (Editeur )
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 |
Résumé :
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.
Codes MSC : 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
|
Informations sur la Vidéo
Réalisateur : Hennenfent, GuillaumeLangue : Anglais Date de publication : 14/09/17 Date de captation : 12/09/17 Sous collection : Research talks arXiv category : Combinatorics ; Optimization and Control ; Computer Science Domaine : Combinatorics ; Computer Science ; Control Theory & Optimization Format : MP4 (.mp4) - HD Durée : 00:54:36 Audience : Researchers Download : https://videos.cirm-math.fr/2017-09-12_Schrijver.mp4 
|
Informations sur la Rencontre
Nom de la rencontre : 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)Organisateurs de la rencontre : Bassino, Frédérique ; Bonomo, Flavia ; Pournin, Lionel ; Valencia-Pabon, Mario ; Vera Lizcano, Juan Carlos Dates : 11/09/17 - 15/09/17 Année de la rencontre : 2017 URL Congrès : http://conferences.cirm-math.fr/1660.html
Données de citation
DOI : 10.24350/CIRM.V.19221703Citer cette vidéo: 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 |
Voir aussi
- [Multi angle] Combinatorial and algorithmic properties of Robinsonian matrices / Auteur de la Conférence Laurent, Monique.
- [Multi angle] Coloring graphs with forbidden induced paths / Auteur de la Conférence Chudnovsky, Maria.
- [Multi angle] Random hyperbolic graphs / Auteur de la Conférence Kiwi, Marcos.
- [Multi angle] Restricted types of matchings / Auteur de la Conférence Rautenbach, Dieter.
Bibliographie
