کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10328699 | 684868 | 2005 | 26 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
A chordal graph H is a triangulation of a graph G if H is obtained by adding edges to G. If no proper subgraph of H is a triangulation of G we call H a minimal triangulation of G. We introduce a new LexBFS-like breadth-first-search algorithm min-LexBFS. We show that variants of min-LexBFS yield linear-time algorithms for computing minimal triangulations of AT-free claw-free graphs and co-comparability graphs. These triangulation algorithms are used to improve approximation algorithms for the bandwidth of AT-free claw-free and co-comparability graphs. We present a certifying recognition algorithm for proper interval graphs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 146, Issue 3, 15 March 2005, Pages 193-218
Journal: Discrete Applied Mathematics - Volume 146, Issue 3, 15 March 2005, Pages 193-218
نویسندگان
Daniel Meister,