Finding an induced subdivision of a digraph

Jørgen Bang-Jensen, Frederic Havet, Nicolas Trotignon

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review

Resumé

We consider the following problem for oriented graphs and digraphs: Given an oriented graph (digraph) H, does it contain an induced subdivision of a prescribed digraph D? The complexity of this problem depends on D and on whether H is an oriented graph or contains 2-cycles. We announce a number of examples of polynomial instances as well as several NP-completeness results.
OriginalsprogEngelsk
TidsskriftElectronic Notes in Discrete Mathematics
Vol/bind37
Sider (fra-til)9-14
ISSN1571-0653
DOI
StatusUdgivet - 2011

Fingeraftryk

Oriented Graph
Subdivision
Digraph
Polynomials
NP-completeness
Cycle
Polynomial

Citer dette

Bang-Jensen, Jørgen ; Havet, Frederic ; Trotignon, Nicolas. / Finding an induced subdivision of a digraph. I: Electronic Notes in Discrete Mathematics. 2011 ; Bind 37. s. 9-14.
@article{99e087bf29f8411193a62debfb185fbe,
title = "Finding an induced subdivision of a digraph",
abstract = "We consider the following problem for oriented graphs and digraphs: Given an oriented graph (digraph) H, does it contain an induced subdivision of a prescribed digraph D? The complexity of this problem depends on D and on whether H is an oriented graph or contains 2-cycles. We announce a number of examples of polynomial instances as well as several NP-completeness results.",
author = "J{\o}rgen Bang-Jensen and Frederic Havet and Nicolas Trotignon",
year = "2011",
doi = "10.1016/j.endm.2011.05.003",
language = "English",
volume = "37",
pages = "9--14",
journal = "Electronic Notes in Discrete Mathematics",
issn = "1571-0653",
publisher = "Heinemann",

}

Finding an induced subdivision of a digraph. / Bang-Jensen, Jørgen; Havet, Frederic ; Trotignon, Nicolas.

I: Electronic Notes in Discrete Mathematics, Bind 37, 2011, s. 9-14.

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review

TY - JOUR

T1 - Finding an induced subdivision of a digraph

AU - Bang-Jensen, Jørgen

AU - Havet, Frederic

AU - Trotignon, Nicolas

PY - 2011

Y1 - 2011

N2 - We consider the following problem for oriented graphs and digraphs: Given an oriented graph (digraph) H, does it contain an induced subdivision of a prescribed digraph D? The complexity of this problem depends on D and on whether H is an oriented graph or contains 2-cycles. We announce a number of examples of polynomial instances as well as several NP-completeness results.

AB - We consider the following problem for oriented graphs and digraphs: Given an oriented graph (digraph) H, does it contain an induced subdivision of a prescribed digraph D? The complexity of this problem depends on D and on whether H is an oriented graph or contains 2-cycles. We announce a number of examples of polynomial instances as well as several NP-completeness results.

U2 - 10.1016/j.endm.2011.05.003

DO - 10.1016/j.endm.2011.05.003

M3 - Journal article

VL - 37

SP - 9

EP - 14

JO - Electronic Notes in Discrete Mathematics

JF - Electronic Notes in Discrete Mathematics

SN - 1571-0653

ER -