کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
434106 689684 2014 15 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Complexity of finding maximum regular induced subgraphs with prescribed degree
ترجمه فارسی عنوان
پیچیدگی یافتن مقادیر منظم الگوریتم های منظم با درجه تجویز شده
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

We study the problem of finding a maximum vertex-subset S of a given graph G   such that the subgraph G[S]G[S] induced by S is r  -regular for a prescribed degree r≥0r≥0. We also consider a variant of the problem which requires G[S]G[S] to be r-regular and connected. Both problems are known to be NP-hard even to approximate for a fixed constant r. In this paper, we thus consider the problems whose input graphs are restricted to some special classes of graphs. We first show that the problems are still NP-hard to approximate even if r is a fixed constant and the input graph is either bipartite or planar. On the other hand, both problems are tractable for graphs having tree-like structures, as follows. We give linear-time algorithms to solve the problems for graphs with bounded treewidth; we note that the hidden constant factor of our running time is just a single exponential of the treewidth. Furthermore, both problems are solvable in polynomial time for chordal graphs.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 550, 18 September 2014, Pages 21–35
نویسندگان
, , , ,