| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 437090 | Theoretical Computer Science | 2012 | 15 Pages |
Abstract
We consider the following problem for oriented graphs and digraphs: given an oriented graph (digraph) G, does it contain an induced subdivision of a prescribed digraph D? The complexity of this problem depends on D and on whether G must be an oriented graph or is allowed to contain 2-cycles. We give a number of examples of polynomial instances as well as several NP-completeness proofs.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
