Finding a subdivision of a digraph

DOI10.1016/J.TCS.2014.10.004zbMATH Open1303.68064OpenAlexW2085634670MaRDI QIDQ476873FDOQ476873

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

Recommendations

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

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)

Cites Work

• Graph theory
• The directed subgraph homeomorphism problem
• Directed tree-width
• Graph minors. XIII: The disjoint paths problem
• Graph structure and monadic second-order logic. A language-theoretic approach
• Finding a long directed cycle
• Parameterized tractability of edge-disjoint paths on directed acyclic graphs
• Title not available (Why is that?)
• Finding an induced subdivision of a digraph
• DAG-Width and Parity Games
• Detecting induced subgraphs
• Packing directed circuits
• Disjoint directed and undirected paths and cycles in digraphs
• Title not available (Why is that?)
• The three-in-a-tree problem
• Highly connected non-2-linked digraphs
• Excluding induced subgraphs
• Parameterized Approximability of the Disjoint Cycle Problem
• Title not available (Why is that?)

Cited In (6)

• DAG-width and circumference of digraphs
• On the complexity of finding internally vertex-disjoint long directed paths
• Finding a subdivision of a prescribed digraph of order 4
• Finding an induced subdivision of a digraph
• Finding good 2-partitions of digraphs. II. Enumerable properties
• Splitting digraphs

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)