Finding a subdivision of a digraph

Jørgen Bang-Jensen; Frederic Havet; Anna- Karolinna Maia

doi:10.1016/j.tcs.2014.10.004

Finding a subdivision of a digraph

Jørgen Bang-Jensen, Frederic Havet, Anna- Karolinna Maia

Department of Mathematics and Computer Science

French Institute for Research in Computer Science and Automation

Research output: Contribution to journal › Journal article › Research › peer-review

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.

Original language	English
Journal	Theoretical Computer Science
Volume	562
Pages (from-to)	283-303
ISSN	0304-3975
DOIs	https://doi.org/10.1016/j.tcs.2014.10.004
Publication status	Published - 2015

Keywords

Linkage problem
Oriented graphs
Subdivision

Documents & Links

10.1016/j.tcs.2014.10.004

https://hal.archives-ouvertes.fr/hal-01111374/document

Cite this

@article{91a614577ab342cebc56cfb9ea452299,

title = "Finding a subdivision of a digraph",

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.",

keywords = "Linkage problem, Oriented graphs, Subdivision",

author = "J{\o}rgen Bang-Jensen and Frederic Havet and Maia, {Anna- Karolinna}",

year = "2015",

doi = "10.1016/j.tcs.2014.10.004",

language = "English",

volume = "562",

pages = "283--303",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier",

}

TY - JOUR

T1 - Finding a subdivision of a digraph

AU - Bang-Jensen, Jørgen

AU - Havet, Frederic

AU - Maia, Anna- Karolinna

PY - 2015

Y1 - 2015

N2 - 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.

AB - 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.

KW - Linkage problem

KW - Oriented graphs

KW - Subdivision

U2 - 10.1016/j.tcs.2014.10.004

DO - 10.1016/j.tcs.2014.10.004

M3 - Journal article

SN - 0304-3975

VL - 562

SP - 283

EP - 303

JO - Theoretical Computer Science

JF - Theoretical Computer Science

ER -

Finding a subdivision of a digraph

Abstract

Keywords

Documents & Links

Fingerprint

Cite this