Skip to Main content Skip to Navigation
Reports

Finding an induced subdivision of a digraph

Abstract : We consider the following problem for oriented graphs and digraphs: Given an oriented graph (digraph) $G$, does it contain an induced subdivision of a prescribed digraph $D$? The complexity of this problem depends on $D$ and on whether $H$ must be an oriented graph or is allowed to contain 2-cycles. We give a number of examples of polynomial instances as well as several NP-completeness proofs
Document type :
Reports
Complete list of metadata

Cited literature [9 references]  Display  Hide  Download

https://hal.inria.fr/inria-00527518
Contributor : Frederic Havet <>
Submitted on : Tuesday, October 19, 2010 - 2:53:39 PM
Last modification on : Monday, December 14, 2020 - 3:30:28 PM
Long-term archiving on: : Friday, October 26, 2012 - 11:45:09 AM

File

RR-7430.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00527518, version 1

Citation

Jørgen Bang-Jensen, Frédéric Havet, Nicolas Trotignon. Finding an induced subdivision of a digraph. [Research Report] RR-7430, INRIA. 2010. ⟨inria-00527518⟩

Share

Metrics

Record views

486

Files downloads

534