Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
436143 | Theoretical Computer Science | 2015 | 21 Pages |
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
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Jørgen Bang-Jensen, Frédéric Havet, A. Karolinna Maia,