Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4952198 | Theoretical Computer Science | 2017 | 8 Pages |
Abstract
Partial k-DAGs are generalizations of partial k-trees. Partial k-trees are undirected graphs with bounded treewidth, whereas partial k-DAGs are digraphs with bounded Kelly-width. It is well-known that an undirected graph is a partial 1-tree if and only if it has no K3 minor. In this paper, we prove that partial 1-DAGs are characterized by three forbidden directed minors, K3, N4 and M5.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Shiva Kintali, Qiuyi Zhang,