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 -