Paper Info
Title
Sufficient conditions for edit-optimal clusters.
Abstract
We give local conditions for clusters in optimal Cluster Editing solutions.Bounded edit degrees is one of the sufficient conditions.An optimality condition for Cluster Deletion is based on degree sequences. Cluster Editing is the problem of turning a graph into a cluster graph, that is, a disjoint union of cliques, by a minimum number of edge edits. Cluster Deletion is similarly defined, with edge deletions only. We propose a local notion of edit-optimality: Informally, we say that a crown (a certain type of labeled graph) is edit-optimal if it yields a cluster in some optimal solution to Cluster Editing, in every graph containing this crown as a subgraph. Then we give sufficient conditions for edit-optimality, e.g., in terms of vertex degrees. A condition for Cluster Deletion applies a theorem of Landau (1953) 7 on degree sequences of tournaments. The conditions are particularly suited for planted models of clusterings, and for networks that only partially exhibit a clear cluster structure.
Year
DOI
Venue
2016
10.1016/j.ipl.2015.12.004
Inf. Process. Lett.
Keywords
DocType
Volume
Graph algorithms,Cluster editing,Optimality criteria,Degree sequence
Journal
116
Issue
ISSN
Citations 
4
0020-0190
1
PageRank 
References 
Authors
0.35
3
1
Name
Order
Citations
PageRank
Peter Damaschke147156.99