کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
431101 | 688275 | 2009 | 19 صفحه PDF | دانلود رایگان |
We consider the concepts of a t-total vertex cover and a t-total edge cover (t⩾1)(t⩾1), which generalise the notions of a vertex cover and an edge cover, respectively. A t-total vertex (respectively edge) cover of a connected graph G is a vertex (edge) cover S of G such that each connected component of the subgraph of G induced by S has at least t vertices (edges). These definitions are motivated by combining the concepts of clustering and covering in graphs. Moreover they yield a spectrum of parameters that essentially range from a vertex cover to a connected vertex cover (in the vertex case) and from an edge cover to a spanning tree (in the edge case). For various values of t , we present NPNP-completeness and approximability results (both upper and lower bounds) and FPTFPT algorithms for problems concerned with finding the minimum size of a t-total vertex cover, t -total edge cover and connected vertex cover, in particular improving on a previous FPTFPT algorithm for the latter problem.
Journal: Journal of Discrete Algorithms - Volume 7, Issue 2, June 2009, Pages 149–167