Standard

Kernelization through tidying : A case study based on s-plex cluster vertex deletion. / Van Bevern, René; Moser, Hannes; Niedermeier, Rolf.

LATIN 2010: Theoretical Informatics - 9th Latin American Symposium, Proceedings. 2010. p. 527-538 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6034 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review

Harvard

Van Bevern, R, Moser, H & Niedermeier, R 2010, Kernelization through tidying: A case study based on s-plex cluster vertex deletion. in LATIN 2010: Theoretical Informatics - 9th Latin American Symposium, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 6034 LNCS, pp. 527-538, 9th Latin American Theoretical Informatics Symposium, LATIN 2010, Oaxaca, Mexico, 19.04.2010. https://doi.org/10.1007/978-3-642-12200-2_46

APA

Van Bevern, R., Moser, H., & Niedermeier, R. (2010). Kernelization through tidying: A case study based on s-plex cluster vertex deletion. In LATIN 2010: Theoretical Informatics - 9th Latin American Symposium, Proceedings (pp. 527-538). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6034 LNCS). https://doi.org/10.1007/978-3-642-12200-2_46

Vancouver

Van Bevern R, Moser H, Niedermeier R. Kernelization through tidying: A case study based on s-plex cluster vertex deletion. In LATIN 2010: Theoretical Informatics - 9th Latin American Symposium, Proceedings. 2010. p. 527-538. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-12200-2_46

Author

Van Bevern, René ; Moser, Hannes ; Niedermeier, Rolf. / Kernelization through tidying : A case study based on s-plex cluster vertex deletion. LATIN 2010: Theoretical Informatics - 9th Latin American Symposium, Proceedings. 2010. pp. 527-538 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@inproceedings{c97da99b9ba54a0d906674c235d11532,
title = "Kernelization through tidying: A case study based on s-plex cluster vertex deletion",
abstract = "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.",
author = "{Van Bevern}, Ren{\'e} and Hannes Moser and Rolf Niedermeier",
year = "2010",
month = jun,
day = "18",
doi = "10.1007/978-3-642-12200-2_46",
language = "English",
isbn = "3642121993",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "527--538",
booktitle = "LATIN 2010",
note = "9th Latin American Theoretical Informatics Symposium, LATIN 2010 ; Conference date: 19-04-2010 Through 23-04-2010",

}

RIS

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 -

ID: 22342309