Finding a subdivision of a digraph

Jørgen Bang-Jensen 1 Frédéric Havet 2 Ana Karolinna Maia 2
2 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
Résumé : Nous considérons le problèmes suivant: étant donné un graphe orienté D, contient-il une subdivision d'un digraphe fixé F? Nous donnons des exemples d'instances polynomiales, plusieurs preuves de NP-complétude ainsi que un certain nombre de conjectures et des problèmes ouverts.
Type de document :
Rapport
[Research Report] RR-8024, INRIA. 2012
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00720500
Contributeur : Ana Karolinna Maia de Oliveira <>
Soumis le : mercredi 25 juillet 2012 - 11:29:35
Dernière modification le : lundi 4 décembre 2017 - 15:14:09
Document(s) archivé(s) le : vendredi 26 octobre 2012 - 02:21:25

Fichier

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

Identifiants

  • HAL Id : hal-00720500, version 2

Collections

Citation

Jørgen Bang-Jensen, Frédéric Havet, Ana Karolinna Maia. Finding a subdivision of a digraph. [Research Report] RR-8024, INRIA. 2012. 〈hal-00720500v2〉

Partager

Métriques

Consultations de la notice

298

Téléchargements de fichiers

223