کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
420555 | 683956 | 2009 | 13 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The clique-separator graph for chordal graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: The clique-separator graph for chordal graphs The clique-separator graph for chordal graphs](/preview/png/420555.png)
چکیده انگلیسی
We present a new representation of a chordal graph called the clique-separator graph , whose nodes are the maximal cliques and minimal vertex separators of the graph. We present structural properties of the clique-separator graph and additional properties when the chordal graph is an interval graph, proper interval graph, or split graph. We also characterize proper interval graphs and split graphs in terms of the clique-separator graph. We present an algorithm that constructs the clique-separator graph of a chordal graph in O(n3)O(n3) time and of an interval graph in O(n2)O(n2) time, where nn is the number of vertices in the graph.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 157, Issue 8, 28 April 2009, Pages 1737–1749
Journal: Discrete Applied Mathematics - Volume 157, Issue 8, 28 April 2009, Pages 1737–1749
نویسندگان
Louis Ibarra,