Subexponential Algorithm for d-Cluster Edge Deletion: Exception or Rule?

Misra, Neeldhara ; Panolan, Fahad ; Saurabh, Saket (2013) Subexponential Algorithm for d-Cluster Edge Deletion: Exception or Rule? In: Mathematical Foundations of Computer Science 2013, August 26-30, 2013, Klosterneuburg, Austria.

Full text not available from this repository.

Official URL: https://10.1007/978-3-642-40313-2_60

Abstract

The correlation clustering problem is a fundamental problem in both theory and practice, and it involves identifying clusters of objects in a data set based on their similarity. A traditional modeling of this question as a graph theoretic problem involves associating vertices with data points and indicating similarity by adjacency. Clusters then correspond to cliques in the graph. The resulting optimization problem, Cluster Editing (and several variants) are very well-studied algorithmically. In many situations, however, translating clusters to cliques can be somewhat restrictive. A more flexible notion would be that of a structure where the vertices are mutually ``not too far apart'', without necessarily being adjacent.

Item Type:Conference or Workshop Item (Paper)
Source:Copyright of this article belongs to Springer Nature Switzerland AG.
ID Code:123358
Deposited On:14 Sep 2021 09:27
Last Modified:14 Sep 2021 09:27

Repository Staff Only: item control page