| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4652581 | Electronic Notes in Discrete Mathematics | 2011 | 6 Pages |
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.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
