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 G 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.
Type de document :
Article dans une revue
Theoretical Computer Science, Elsevier, 2012, 443, pp.10--24
Liste complète des métadonnées

Littérature citée [10 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00749187
Contributeur : Frederic Havet <>
Soumis le : dimanche 23 octobre 2016 - 15:57:33
Dernière modification le : jeudi 17 mai 2018 - 12:52:03

Fichier

subdiv-revise.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00749187, version 1

Collections

Citation

Jørgen Bang-Jensen, Frédéric Havet, Nicolas Trotignon. Finding an induced subdivision of a digraph.. Theoretical Computer Science, Elsevier, 2012, 443, pp.10--24. 〈hal-00749187〉

Partager

Métriques

Consultations de la notice

287

Téléchargements de fichiers

93