Finding a subdivision of a digraph

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

Research output: Contribution to journalJournal articleResearchpeer-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 languageEnglish
JournalTheoretical Computer Science
Volume562
Pages (from-to)283-303
ISSN0304-3975
DOIs
Publication statusPublished - 2015

    Fingerprint

Cite this