HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
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 Connect in order to contact the contributor
Submitted on : Tuesday, October 19, 2010 - 2:53:39 PM
Last modification on : Friday, February 4, 2022 - 3:11:36 AM
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

201

Files downloads

261