Finding an induced subdivision of a digraph

DOI10.1016/j.endm.2011.05.003zbMath1268.05191arXiv1309.1553OpenAlexW2884902798MaRDI QIDQ5891097

Frédéric Havet, Nicolas Trotignon, Jörgen Bang-Jensen

Publication date: 23 July 2013

Published in: Electronic Notes in Discrete Mathematics, Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1309.1553

zbMATH Keywords

NP-completenessdigraphs3-SATinduced paths and cycleslinkings

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Paths and cycles (05C38) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20)

Related Items (7)

Topological indices of the line graph of subdivision graphs and their Schur-bounds ⋮ Finding an induced subdivision of a digraph ⋮ Finding a subdivision of a digraph ⋮ Unnamed Item ⋮ Miscellaneous Digraph Classes ⋮ Perfect Digraphs ⋮ Point partition numbers: perfect graphs

Cites Work

• Unnamed Item
• Unnamed Item
• The three-in-a-tree problem
• Induced disjoint paths problem in a planar digraph
• Disjoint directed and undirected paths and cycles in digraphs
• The directed subgraph homeomorphism problem
• On the complexity of testing for odd holes and induced odd paths
• Corrigendum to: On the complexity of testing for odd holes and induced odd paths
• Graph minors. XIII: The disjoint paths problem
• Finding an induced subdivision of a digraph
• Detecting induced subgraphs

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