Graph-based data clustering: a quadratic-vertex problem kernel for s-Plex Cluster Vertex Deletion

Details Graph-based data clustering: a quadratic-vertex problem kernel for s-Plex Cluster Vertex Deletion Graph-based data clustering: a quadratic-vertex problem kernel for s-Plex Cluster Vertex Deletion

2009-09-15

arxiv.org/abs/0909.2814v1

Computer Science

Discrete Mathematics

41 pages, 17 figures

Scientific paper

10.1007/s00453-011-9492-7

We introduce the s-Plex Cluster Vertex Deletion problem. Like the Cluster Vertex Deletion problem, it is NP-hard and motivated by graph-based data clustering. While the task in Cluster Vertex Deletion is to delete vertices from a graph so that its connected components become cliques, the task in s-Plex Cluster Vertex Deletion is to delete vertices from a graph so that its connected components become s-plexes. An s-plex is a graph in which every vertex is nonadjacent to at most s-1 other vertices; a clique is an 1-plex. In contrast to Cluster Vertex Deletion, s-Plex Cluster Vertex Deletion allows to balance the number of vertex deletions against the sizes and the density of the resulting clusters, which are s-plexes instead of cliques. The focus of this work is the development of provably efficient and effective data reduction rules for s-Plex Cluster Vertex Deletion. In terms of fixed-parameter algorithmics, these yield a so-called problem kernel. A similar problem, s-Plex Editing, where the task is the insertion or the deletion of edges so that the connected components of a graph become s-plexes, has also been studied in terms of fixed-parameter algorithmics. Using the number of allowed graph modifications as parameter, we expect typical parameter values for s-Plex Cluster Vertex Deletion to be significantly lower than for s-Plex Editing, because one vertex deletion can lead to a high number of edge deletions. This holds out the prospect for faster fixed-parameter algorithms for s-Plex Cluster Vertex Deletion.

Affiliated with

Also associated with

No associations

Rating

Graph-based data clustering: a quadratic-vertex problem kernel for s-Plex Cluster Vertex Deletion does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Graph-based data clustering: a quadratic-vertex problem kernel for s-Plex Cluster Vertex Deletion, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Graph-based data clustering: a quadratic-vertex problem kernel for s-Plex Cluster Vertex Deletion will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-556011