کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
436283 | 689984 | 2009 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Minimal interval completion through graph exploration
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
Given an arbitrary graph G=(V,E) and an interval graph H=(V,F) with E⊆F we say that H is an interval completion of G. The graph H is called a minimal interval completion of G if, for any sandwich graph H′=(V,F′) with E⊆F′⊂F, H′ is not an interval graph. In this paper we give a O(nm) time algorithm computing a minimal interval completion of an arbitrary graph. The output is an interval model of the completion.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 410, Issue 1, 28 January 2009, Pages 35-43
Journal: Theoretical Computer Science - Volume 410, Issue 1, 28 January 2009, Pages 35-43