کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
420476 | 683945 | 2009 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Finding induced trees
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
Let G=(V(G),E(G))G=(V(G),E(G)) be a finite connected undirected graph and W⊂V(G)W⊂V(G) a subset of vertices. We are searching for a subset X⊂V(G)X⊂V(G) such that W⊂XW⊂X and the subgraph induced on XX is a tree. NPNP-completeness results and polynomial time algorithms are given assuming that the cardinality of WW is fixed or not. Besides we give complexity results when XX has to induce a path or when GG is a weighted graph. We also consider problems where the cardinality of XX has to be minimized.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 157, Issue 17, 28 October 2009, Pages 3552–3557
Journal: Discrete Applied Mathematics - Volume 157, Issue 17, 28 October 2009, Pages 3552–3557
نویسندگان
N. Derhy, C. Picouleau,