کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
421110 | 684142 | 2015 | 12 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Efficiently decomposing, recognizing and triangulating hole-free graphs without diamonds
ترجمه فارسی عنوان
گرافیک بدون سوراخ بدون الماس به طور قابل ملاحظه ای تجزیه، تشخیص و سه بعدی سازی می شود
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
A graph is hole- and diamond-free (HD-free) if none of its induced subgraphs is isomorphic to a chordless cycle of length at least five or to a diamond. Using the clique separator approach and the simple structure of atoms of HD-free graphs, we show how to recognize HD-free graphs in time O(n2)O(n2). One of the main tools is Lexicographic Breadth-First Search (LexBFS); we give two new properties of LexBFS which are essential for reaching the time bound and which hold for any graph. Moreover, we find minimal triangulations of HD-free graphs in time O(n2)O(n2), introducing efficient algorithms for the minimal triangulation of matched co-bipartite graphs and chordal bipartite graphs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 184, 31 March 2015, Pages 50–61
Journal: Discrete Applied Mathematics - Volume 184, 31 March 2015, Pages 50–61
نویسندگان
Anne Berry, Andreas Brandstädt, Vassilis Giakoumakis, Frédéric Maffray,