کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
421053 | 684022 | 2006 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On the interval completion of chordal graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
For a given graph G=(V,E)G=(V,E), the interval completion problem of G is to find an edge set F such that the supergraph H=(V,E∪F)H=(V,E∪F) of G is an interval graph and |F||F| is minimum. It has been shown that it is equivalent to the minimum sum cut problem, the profile minimization problem and a kind of graph searching problems. Furthermore, it has applications in computational biology, archaeology, and clone fingerprinting. In this paper, we show that it is NP-complete on split graphs and propose an efficient algorithm on primitive starlike graphs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 154, Issue 6, 15 April 2006, Pages 1003–1010
Journal: Discrete Applied Mathematics - Volume 154, Issue 6, 15 April 2006, Pages 1003–1010
نویسندگان
Sheng-Lung Peng, Chi-Kang Chen,