TY - GEN
T1 - Kernelization through tidying
T2 - 9th Latin American Theoretical Informatics Symposium, LATIN 2010
AU - Van Bevern, René
AU - Moser, Hannes
AU - Niedermeier, Rolf
PY - 2010/6/18
Y1 - 2010/6/18
N2 - We introduce the NP-hard graph-based data clustering problem s -Plex Cluster Vertex Deletion, where the task is to delete at most k vertices from a graph so that the connected components of the resulting graph are s-plexes. In an s-plex, every vertex has an edge to all but at most s∈-∈1 other vertices; cliques are 1-plexes. We propose a new method for kernelizing a large class of vertex deletion problems and illustrate it by developing an O(k 2 s3)-vertex problem kernel for s -Plex Cluster Vertex Deletion that can be computed in O(ksn2) time, where n is the number of graph vertices. The corresponding "kernelization through tidying" exploits polynomial-time approximation results.
AB - We introduce the NP-hard graph-based data clustering problem s -Plex Cluster Vertex Deletion, where the task is to delete at most k vertices from a graph so that the connected components of the resulting graph are s-plexes. In an s-plex, every vertex has an edge to all but at most s∈-∈1 other vertices; cliques are 1-plexes. We propose a new method for kernelizing a large class of vertex deletion problems and illustrate it by developing an O(k 2 s3)-vertex problem kernel for s -Plex Cluster Vertex Deletion that can be computed in O(ksn2) time, where n is the number of graph vertices. The corresponding "kernelization through tidying" exploits polynomial-time approximation results.
UR - http://www.scopus.com/inward/record.url?scp=77953530688&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-12200-2_46
DO - 10.1007/978-3-642-12200-2_46
M3 - Conference contribution
AN - SCOPUS:77953530688
SN - 3642121993
SN - 9783642121999
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 527
EP - 538
BT - LATIN 2010
Y2 - 19 April 2010 through 23 April 2010
ER -