Skip to Main content Skip to Navigation
Reports

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 , 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.
Complete list of metadatas

Cited literature [19 references]  Display  Hide  Download

https://hal.inria.fr/hal-00720500
Contributor : Ana Karolinna Maia de Oliveira <>
Submitted on : Wednesday, July 25, 2012 - 11:29:35 AM
Last modification on : Tuesday, May 26, 2020 - 6:50:22 PM
Long-term archiving on: : Friday, October 26, 2012 - 2:21:25 AM

File

RR-8024.pdf
Files produced by the author(s)

Identifiers

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

Share

Metrics

Record views

438

Files downloads

685