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


https://hal.inria.fr/hal-00749187
Contributeur : Frederic Havet <>
Soumis le : dimanche 23 octobre 2016 - 15:57:33
Dernière modification le : mercredi 26 octobre 2016 - 01:11:28

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

236

Téléchargements du document

80