Disjoint paths in symmetric digraphs

DOI10.1016/J.DAM.2008.04.024zbMATH Open1229.05171OpenAlexW1968740157MaRDI QIDQ1003758FDOQ1003758

Authors: Aubin Jarry, Stéphane Pérennes 

Publication date: 4 March 2009

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2008.04.024

Recommendations

• Disjoint \(A\)-paths in digraphs
• Disjoint paths in acyclic digraphs
• Disjoint paths in decomposable digraphs
• Disjoint paths in graphs
• scientific article; zbMATH DE number 4089593
• Disjoint paths in graphs. (Reprint)
• Disjoint directed and undirected paths and cycles in digraphs
• Disjoint paths in graphs. II: A special case
• Disjoint shortest paths in graphs
• Disjoint paths in sparse graphs

zbMATH Keywords

disjoint pathssymmetric digraphs

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Paths and cycles (05C38)

Cites Work

• Graph Classes: A Survey
• The directed subgraph homeomorphism problem
• Graph minors. XIII: The disjoint paths problem
• A Polynomial Solution to the Undirected Two Paths Problem
• On the Complexity of Timetable and Multicommodity Flow Problems
• The edge-disjoint paths problem is NP-complete for series-parallel graphs
• On the complexity of the disjoint paths problem
• On the Computational Complexity of Combinatorial Problems
• Finding Two Disjoint Paths Between Two Pairs of Vertices in a Graph
• NP-completeness of some edge-disjoint paths problems
• Title not available (Why is that?)
• The subgraph homeomorphism problem
• Multicommodity flows in certain planar directed networks
• Weak Three-Linking in Eulerian Dgraphs

Cited In (6)

• Disjoint \(A\)-paths in digraphs
• Multiflows in symmetric digraphs
• Disjoint non-balanced \(A\)-paths in biased graphs
• Computing monotone disjoint paths on polytopes
• Edge-disjoint paths in digraphs with bounded independence number
• A relaxation of the directed disjoint paths problem: a global congestion metric helps

This page was built for publication: Disjoint paths in symmetric digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1003758)