کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
431044 | 688259 | 2011 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Contracting planar graphs to contractions of triangulations
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
For every graph H, there exists a polynomial-time algorithm deciding if a planar input graph G can be contracted to H. However, the degree of the polynomial depends on the size of H . We identify a class of graphs CC such that for every fixed H∈CH∈C, there exists a linear-time algorithm deciding whether a given planar graph G can be contracted to H . The class CC is the closure of planar triangulated graphs under taking of contractions. In fact, we prove that a graph H∈CH∈C if and only if there exists a constant cHcH such that if the treewidth of a graph is at least cHcH, it contains H as a contraction. We also provide a characterization of CC in terms of minimal forbidden contractions.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Discrete Algorithms - Volume 9, Issue 3, September 2011, Pages 299–306
Journal: Journal of Discrete Algorithms - Volume 9, Issue 3, September 2011, Pages 299–306
نویسندگان
Marcin Kamiński, Daniël Paulusma, Dimitrios M. Thilikos,