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 Catégorie arXiv : Combinatorics ; Optimization and Control ; Computer Science Domaine(s) : Combinatoires ; Informatique ; Théorie du Contrôle & Optimisation Format : MP4 (.mp4) - HD Durée : 00:54:36 Audience : Chercheurs 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 de la Rencontre : 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
