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

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