Finding an induced subdivision of a digraph

Frédéric Havet 1 Jørgen Bang-Jensen 2 Nicolas Trotignon 3
1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
2 IMADA - Department of Mathematics and Computer Science [Odense]
3 LIAFA - Laboratoire d'informatique Algorithmique : Fondements et Applications
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.
Keywords : digraphs NP-completeness induced paths and cycles linkings
Type de document :
Communication dans un congrès
Electronic Notes on Discrete Mathematics. VI Latin-American Algorithms, Graphs and Optimization Symposium (LAGOS 2011), Apr 2011, Bariloche, Argentina. 37, pp.09--14, 2011
Liste complète des métadonnées
https://hal.inria.fr/inria-00638464
Contributeur : Frederic Havet <>
Soumis le : vendredi 4 novembre 2011 - 18:42:10
Dernière modification le : jeudi 15 décembre 2016 - 01:07:34

Identifiants

  • HAL Id : inria-00638464, version 1

Collections

INRIA | I3S | LIAFA | UNICE | TDS-MACS | USPC

Citation

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

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

131

Contact


archive-ouverte@inria.fr