F Nous contacter


H 2 The partially disjoint paths problem

Auteurs : Schrijver, Alexander (Auteur de la Conférence)
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, Guillaume
    Langue : Anglais
    Date de publication : 14/09/17
    Date de captation : 12/09/17
    Collection : Research talks
    Format : MP4 (.mp4) - HD
    Durée : 00:54:36
    Domaine : Combinatorics ; Computer Science ; Control Theory & Optimization
    Audience : Chercheurs ; Doctorants , Post - Doctorants
    Download : http://videos.cirm-math.fr/2017-09-12_Schrijver.mp4

Informations sur la rencontre

Nom du congrès : 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)
Organisteurs Congrès : 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

Citation Data

DOI : 10.24350/CIRM.V.19221703
Cite 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

Voir aussi