HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information

# Finding an induced subdivision of a digraph

2 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
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

Cited literature [9 references]

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⟩

Record views