Finding a subdivision of a digraph

Jørgen Bang-Jensen 1 Frédéric Havet 2 Ana Karolinna Maia de Oliveira 2
2 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : We consider the following problem for oriented graphs and digraphs: Given a directed graph D, does it contain a subdivision of a prescribed digraph F? We give a number of examples of polynomial instances, several NP-completeness proofs as well as a number of conjectures and open problems.
Type de document :
Article dans une revue
Theoretical Computer Science, Elsevier, 2015, 562, pp.20
Liste complète des métadonnées

https://hal.inria.fr/hal-01111374
Contributeur : Frederic Havet <>
Soumis le : dimanche 23 octobre 2016 - 15:41:06
Dernière modification le : mardi 25 octobre 2016 - 01:05:06

Fichier

subdivision.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01111374, version 1

Collections

Citation

Jørgen Bang-Jensen, Frédéric Havet, Ana Karolinna Maia de Oliveira. Finding a subdivision of a digraph. Theoretical Computer Science, Elsevier, 2015, 562, pp.20. <hal-01111374>

Partager

Métriques

Consultations de
la notice

168

Téléchargements du document

73