Finding a subdivision of a digraph

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

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review

Abstrakt

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.
OriginalsprogEngelsk
TidsskriftTheoretical Computer Science
Vol/bind562
Sider (fra-til)283-303
ISSN0304-3975
DOI
StatusUdgivet - 2015

    Fingerprint

Citationsformater