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 $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
Type de document :
Rapport
[Research Report] RR-7430, INRIA. 2010
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00527518
Contributeur : Frederic Havet <>
Soumis le : mardi 19 octobre 2010 - 14:53:39
Dernière modification le : mercredi 31 janvier 2018 - 10:24:04
Document(s) archivé(s) le : vendredi 26 octobre 2012 - 11:45:09

Fichier

RR-7430.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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〉

Partager

Métriques

Consultations de la notice

351

Téléchargements de fichiers

193