Standard

Approximation and tidying—a problem kernel for s-Plex cluster vertex deletion. / van Bevern, René; Moser, Hannes; Niedermeier, Rolf.

в: Algorithmica, Том 62, № 3-4, 01.01.2012, стр. 930-950.

Результаты исследований: Научные публикации в периодических изданияхстатьяРецензирование

Harvard

van Bevern, R, Moser, H & Niedermeier, R 2012, 'Approximation and tidying—a problem kernel for s-Plex cluster vertex deletion', Algorithmica, Том. 62, № 3-4, стр. 930-950. https://doi.org/10.1007/s00453-011-9492-7

APA

Vancouver

van Bevern R, Moser H, Niedermeier R. Approximation and tidying—a problem kernel for s-Plex cluster vertex deletion. Algorithmica. 2012 янв. 1;62(3-4):930-950. doi: 10.1007/s00453-011-9492-7

Author

van Bevern, René ; Moser, Hannes ; Niedermeier, Rolf. / Approximation and tidying—a problem kernel for s-Plex cluster vertex deletion. в: Algorithmica. 2012 ; Том 62, № 3-4. стр. 930-950.

BibTeX

@article{4c25c61b1d40462a993e6224f5887877,
title = "Approximation and tidying—a problem kernel for 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 based on “approximation and tidying” for kernelizing vertex deletion problems whose goal graphs can be characterized by forbidden induced subgraphs. The method exploits polynomial-time approximation results and thus provides a useful link between approximation and kernelization. Employing “approximation and tidying”, we develop data reduction rules that, in O(ksn2) time, transform an s-PLEX CLUSTER VERTEX DELETION instance with n vertices into an equivalent instance with O(k2s3) vertices, yielding a problem kernel. To this end, we also show how to exploit structural properties of the specific problem in order to significantly improve the running time of the proposed kernelization method.",
keywords = "Computational intractability, Fixed-parameter tractability, Graph-based data clustering, NP-hard graph problem, Polynomial-time data reduction",
author = "{van Bevern}, Ren{\'e} and Hannes Moser and Rolf Niedermeier",
year = "2012",
month = jan,
day = "1",
doi = "10.1007/s00453-011-9492-7",
language = "English",
volume = "62",
pages = "930--950",
journal = "Algorithmica",
issn = "0178-4617",
publisher = "Springer New York",
number = "3-4",

}

RIS

TY - JOUR

T1 - Approximation and tidying—a problem kernel for s-Plex cluster vertex deletion

AU - van Bevern, René

AU - Moser, Hannes

AU - Niedermeier, Rolf

PY - 2012/1/1

Y1 - 2012/1/1

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 based on “approximation and tidying” for kernelizing vertex deletion problems whose goal graphs can be characterized by forbidden induced subgraphs. The method exploits polynomial-time approximation results and thus provides a useful link between approximation and kernelization. Employing “approximation and tidying”, we develop data reduction rules that, in O(ksn2) time, transform an s-PLEX CLUSTER VERTEX DELETION instance with n vertices into an equivalent instance with O(k2s3) vertices, yielding a problem kernel. To this end, we also show how to exploit structural properties of the specific problem in order to significantly improve the running time of the proposed kernelization method.

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 based on “approximation and tidying” for kernelizing vertex deletion problems whose goal graphs can be characterized by forbidden induced subgraphs. The method exploits polynomial-time approximation results and thus provides a useful link between approximation and kernelization. Employing “approximation and tidying”, we develop data reduction rules that, in O(ksn2) time, transform an s-PLEX CLUSTER VERTEX DELETION instance with n vertices into an equivalent instance with O(k2s3) vertices, yielding a problem kernel. To this end, we also show how to exploit structural properties of the specific problem in order to significantly improve the running time of the proposed kernelization method.

KW - Computational intractability

KW - Fixed-parameter tractability

KW - Graph-based data clustering

KW - NP-hard graph problem

KW - Polynomial-time data reduction

UR - http://www.scopus.com/inward/record.url?scp=79251532855&partnerID=8YFLogxK

U2 - 10.1007/s00453-011-9492-7

DO - 10.1007/s00453-011-9492-7

M3 - Article

AN - SCOPUS:79251532855

VL - 62

SP - 930

EP - 950

JO - Algorithmica

JF - Algorithmica

SN - 0178-4617

IS - 3-4

ER -

ID: 22341567