کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
421277 | 684176 | 2010 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The kk-in-a-tree problem for graphs of girth at least kk
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
For all integers k≥3k≥3, we give an O(n4)O(n4)-time algorithm for the problem whose instance is a graph GG of girth at least kk together with kk vertices and whose question is “Does GG contains an induced subgraph containing the kk vertices and isomorphic to a tree?”.This directly follows for k=3k=3 from the three-in-a-tree algorithm of Chudnovsky and Seymour and for k=4k=4 from a result of Derhy, Picouleau and Trotignon. Here we solve the problem for k≥5k≥5. Our algorithm relies on a structural description of graphs of girth at least kk that do not contain an induced tree covering kk given vertices (k≥5k≥5).
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 158, Issue 15, 6 August 2010, Pages 1644–1649
Journal: Discrete Applied Mathematics - Volume 158, Issue 15, 6 August 2010, Pages 1644–1649
نویسندگان
W. Liu, N. Trotignon,