کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
418629 | 681701 | 2010 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Recognizing digraphs of Kelly-width 2
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
Kelly-width is a parameter of digraphs recently proposed by Hunter and Kreutzer as a directed analogue of treewidth. We give an alternative characterization of digraphs of bounded Kelly-width in support of this analogy, and the first polynomial-time algorithm recognizing digraphs of Kelly-width 2. For an input digraph G=(V,A)G=(V,A) the algorithm outputs a vertex ordering and a digraph H=(V,B)H=(V,B) with A⊆BA⊆B witnessing either that GG has Kelly-width at most 2 or that GG has Kelly-width at least 3, in time linear in HH.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 158, Issue 7, 6 April 2010, Pages 741–746
Journal: Discrete Applied Mathematics - Volume 158, Issue 7, 6 April 2010, Pages 741–746
نویسندگان
Daniel Meister, Jan Arne Telle, Martin Vatshelle,