Skip to Main content Skip to Navigation
Conference papers

Finding an induced subdivision of a digraph

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

https://hal.inria.fr/inria-00638464
Contributor : Frederic Havet <>
Submitted on : Friday, November 4, 2011 - 6:42:10 PM
Last modification on : Monday, December 14, 2020 - 3:30:28 PM

Identifiers

  • HAL Id : inria-00638464, version 1

Citation

Frédéric Havet, Jørgen Bang-Jensen, Nicolas Trotignon. Finding an induced subdivision of a digraph. VI Latin-American Algorithms, Graphs and Optimization Symposium (LAGOS 2011), Apr 2011, Bariloche, Argentina. pp.09--14. ⟨inria-00638464⟩

Share

Metrics

Record views

272