<XML><RECORDS><RECORD><REFERENCE_TYPE>0</REFERENCE_TYPE><REFNUM>8967</REFNUM><AUTHORS><AUTHOR>Fernau,H.</AUTHOR><AUTHOR>Manlove,D.F.</AUTHOR></AUTHORS><YEAR>2009</YEAR><TITLE>Vertex and edge covers with clustering properties: complexity and algorithms</TITLE><PLACE_PUBLISHED>Journal of Discrete Algorithms, volume 7, number 2</PLACE_PUBLISHED><PUBLISHER>Elsevier Science</PUBLISHER><PAGES>149-167</PAGES><LABEL>Fernau:2009:8967</LABEL><KEYWORDS><KEYWORD>Algorithm; NP-completeness; approximability; t-total vertex cover; connected vertex cover; t-total edge cover</KEYWORD></KEYWORDS<ABSTRACT>We consider the concepts of a t-total vertex cover and a t- total edge cover (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 NP-completeness and approximability results (both upper and lower bounds) and FPT 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 FPT algorithm for the latter problem.</ABSTRACT><URL>http://dx.doi.org/10.1016/j.jda.2008.09.007</URL></RECORD></RECORDS></XML>