Skip to Main content Skip to Navigation

# 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
Complete list of metadata

Cited literature [9 references]

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⟩

Record views

Files downloads