NDLI: A More Relaxed Model for Graph-Based Data Clustering: s-Plex Cluster Editing

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Komusiewicz, Christian Niedermeier, Rolf Guo, Jiong Uhlmann, Johannes
Copyright Year	2010
Abstract	We introduce the s-Plex Cluster Editing problem as a generalization of the well-studied Cluster Editing problem; both are NP-hard and both are motivated by graph-based data clustering. Instead of transforming a given graph by a minimum number of edge modifications into a disjoint union of cliques (this is Cluster Editing), the task in the case of s-Plex Cluster Editing is to transform a graph into a cluster graph consisting of a disjoint union of so-called s-plexes. Herein, an s-plex is a vertex set S inducing a subgraph in which every vertex has degree at least $\|S\|-s$. Cliques are 1-plexes. The advantage of s-plexes for $s\geq2$ is that they allow us to model a more relaxed cluster notion (s-plexes instead of cliques), better reflecting inaccuracies of the input data. We develop a provably effective preprocessing based on data reduction (yielding a so-called problem kernel), a forbidden subgraph characterization of s-plex cluster graphs, and a depth-bounded search tree which is used to find optimal edge modification sets. Altogether, this yields efficient algorithms in case of moderate numbers of edge modifications; this is often a reasonable assumption under a maximum parsimony model for data clustering.
Starting Page	1662
Ending Page	1683
Page Count	22
File Format	PDF
ISSN	08954801
DOI	10.1137/090767285
e-ISSN	10957146
Journal	SIAM Journal on Discrete Mathematics (SJDMEC)
Issue Number	4
Volume Number	24
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2010-12-08
Access Restriction	Subscribed
Subject Keyword	data reduction exact algorithms NP-hard problems k-plex graph modification fixed-parameter tractability Graph theory Graph algorithms forbidden subgraph characterization dense subgraphs
Content Type	Text
Resource Type	Article
Subject	Mathematics

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

A more relaxed model for graph-based data clustering: s-plex editing (2009)

Graph-Based Data Clustering with Overlaps (2009)

Graph-modeled data clustering: Fixed-parameter algorithms for clique generation (2003)

Graph-based data clustering: a quadratic-vertex problem kernel for s-plex cluster vertex deletion (2009).

Fixed-Parameter Algorithms for Graph-Modeled Data Clustering (2009)

Graph-modeled data clustering: Fixed-parameter algorithms for clique generation (2003)

A more effective linear kernelization for cluster editing (2007)

Exact algorithms for cluster editing: Evaluation and experiments (2008)

Exact algorithms for cluster editing: Evaluation and experiments

A More Relaxed Model for Graph-Based Data Clustering: s-Plex Cluster Editing

Similar Documents

A more relaxed model for graph-based data clustering: s-plex editing (2009)

Graph-Based Data Clustering with Overlaps (2009)

Graph-modeled data clustering: Fixed-parameter algorithms for clique generation (2003)

Graph-based data clustering: a quadratic-vertex problem kernel for s-plex cluster vertex deletion (2009).

Fixed-Parameter Algorithms for Graph-Modeled Data Clustering (2009)

Graph-modeled data clustering: Fixed-parameter algorithms for clique generation (2003)

A more effective linear kernelization for cluster editing (2007)

Exact algorithms for cluster editing: Evaluation and experiments (2008)

Exact algorithms for cluster editing: Evaluation and experiments

A More Relaxed Model for Graph-Based Data Clustering: s-Plex Cluster Editing