Skip to Main content Skip to Navigation
New interface
Reports (Research report)

Finding a subdivision of a digraph

Jørgen Bang-Jensen 1 Frédéric Havet 2 Ana Karolinna Maia de Oliviera 2 
2 MASCOTTE - Algorithms, simulation, combinatorics and optimization 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 :
Reports (Research report)
Complete list of metadata

Cited literature [19 references]  Display  Hide  Download
Contributor : Ana Karolinna Maia De Oliveira Connect in order to contact the contributor
Submitted on : Wednesday, July 25, 2012 - 11:29:35 AM
Last modification on : Wednesday, October 26, 2022 - 8:16:09 AM
Long-term archiving on: : Friday, October 26, 2012 - 2:21:25 AM


Files produced by the author(s)


  • HAL Id : hal-00720500, version 2


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



Record views


Files downloads