CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Sufficient conditions for edit-optimal clusters

Peter Damaschke (Institutionen för data- och informationsteknik, Datavetenskap, Algoritmer (Chalmers))
Information Processing Letters (0020-0190). Vol. 116 (2016), 4, p. 267-272.
[Artikel, refereegranskad vetenskaplig]

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) 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.

Nyckelord: graph algorithms, cluster editing, optimality criteria, degree sequence

Denna post skapades 2016-01-20. Senast ändrad 2016-03-09.
CPL Pubid: 230977


Läs direkt!

Länk till annan sajt (kan kräva inloggning)