Finding a subdivision of a digraph

DOI10.1016/j.tcs.2014.10.004zbMath1303.68064OpenAlexW2085634670MaRDI QIDQ476873

Frédéric Havet, A. Karolinna Maia, Jörgen Bang-Jensen

Publication date: 2 December 2014

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

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

zbMATH Keywords

subdivisionoriented graphslinkage problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Directed graphs (digraphs), tournaments (05C20)

Related Items (3)

Finding good 2-partitions of digraphs. II. Enumerable properties ⋮ On the complexity of finding internally vertex-disjoint long directed paths ⋮ DAG-Width and Circumference of Digraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The three-in-a-tree problem
• Disjoint directed and undirected paths and cycles in digraphs
• The directed subgraph homeomorphism problem
• Highly connected non-2-linked digraphs
• Packing directed circuits
• Directed tree-width
• Graph minors. XIII: The disjoint paths problem
• Finding a long directed cycle
• Parameterized Approximability of the Disjoint Cycle Problem
• DAG-Width and Parity Games
• Finding an induced subdivision of a digraph
• Algorithms - ESA 2003
• Detecting induced subgraphs

This page was built for publication: Finding a subdivision of a digraph