Skip to Main content Skip to Navigation
Journal articles

Finding a subdivision of a digraph

Jørgen Bang-Jensen 1 Frédéric Havet 2 Ana Karolinna Maia de Oliviera 2
2 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - 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.
Document type :
Journal articles
Complete list of metadata

Cited literature [9 references]  Display  Hide  Download
Contributor : Frederic Havet Connect in order to contact the contributor
Submitted on : Sunday, October 23, 2016 - 3:41:06 PM
Last modification on : Tuesday, May 18, 2021 - 12:04:01 PM


Files produced by the author(s)


  • HAL Id : hal-01111374, version 1




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



Record views


Files downloads