Finding a subdivision of a digraph

DOI10.1016/J.TCS.2014.10.004MaRDI QIDQ476873zbMATHOpenAlexFDO

Authors 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

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

Recommendations

• Finding a subdivision of a prescribed digraph of order 4
• Subdivisions of transitive tournaments
• A note on complete subdivisions in digraphs of large outdegree

Cites work

• scientific article; zbMATH DE number 475591 (Why is no real title available?)
• scientific article; zbMATH DE number 6469131 (Why is no real title available?)
• scientific article; zbMATH DE number 3225808 (Why is no real title available?)
• DAG-Width and Parity Games
• Directed tree-width
• Disjoint directed and undirected paths and cycles in digraphs
• Excluding induced subgraphs
• Finding a long directed cycle
• Graph minors. XIII: The disjoint paths problem
• Graph structure and monadic second-order logic. A language-theoretic approach
• Graph theory
• Highly connected non-2-linked digraphs
• Packing directed circuits
• Parameterized Approximability of the Disjoint Cycle Problem
• Parameterized tractability of edge-disjoint paths on directed acyclic graphs
• The directed subgraph homeomorphism problem
• The three-in-a-tree problem

Cited in

(4)

• DAG-width and circumference of digraphs
• Splitting digraphs
• Finding good 2-partitions of digraphs. II. Enumerable properties
• Finding a subdivision of a prescribed digraph of order 4

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

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