کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4952198 | 1442027 | 2017 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Forbidden directed minors and Kelly-width
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 662, 1 February 2017, Pages 40-47
Journal: Theoretical Computer Science - Volume 662, 1 February 2017, Pages 40-47
نویسندگان
Shiva Kintali, Qiuyi Zhang,