Disjoint directed and undirected paths and cycles in digraphs

DOI10.1016/j.tcs.2009.08.034zbMath1176.68137OpenAlexW2075073335MaRDI QIDQ1034635

Matthias Kriesell, Jörgen Bang-Jensen

Publication date: 6 November 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2009.08.034

zbMATH Keywords

NP-completenessmixed graphssubgraph homeomorphism problemdichotomy resultdisjoint paths in digraphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (11)

Vertex-disjoint directed and undirected cycles in general digraphs ⋮ On the problem of finding disjoint cycles and dicycles in a digraph ⋮ Arc-disjoint spanning sub(di)graphs in digraphs ⋮ Digraph width measures in parameterized algorithmics ⋮ Arc-disjoint paths and trees in 2-regular digraphs ⋮ Finding an induced subdivision of a digraph ⋮ Finding a subdivision of a digraph ⋮ Arc-Disjoint Directed and Undirected Cycles in Digraphs ⋮ On Digraph Width Measures in Parameterized Algorithmics ⋮ Acyclic Digraphs ⋮ Disjoint sub(di)graphs in digraphs

Cites Work

• Unnamed Item
• Unnamed Item
• The directed subgraph homeomorphism problem
• Graph minors. XIII: The disjoint paths problem
• On the problem of finding disjoint cycles and dicycles in a digraph
• Finding Two Disjoint Paths Between Two Pairs of Vertices in a Graph
• Digraphs

This page was built for publication: Disjoint directed and undirected paths and cycles in digraphs