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

Cluster editing with locally bounded modifications revisited

Peter Damaschke (Institutionen för data- och informationsteknik, Datavetenskap, Algoritmer (Chalmers))
24th International Workshop on Combinatorial Algorithms IWOCA 2013, Lecture Notes in Computer Science Vol. 8288 (2013), p. 433-437.
[Konferensbidrag, refereegranskat]

For Cluster Editing where both the number of clusters and the edit degree are bounded, we speed up the kernelization by almost a factor n compared to Komusiewicz and Uhlmann (2012), at cost of a marginally worse kernel size bound. We also give sufficient conditions for a subset of vertices to be a cluster in some optimal clustering.

Nyckelord: cluster editing, edit degree, kernelization, list edge coloring



Denna post skapades 2013-11-29. Senast ändrad 2015-02-11.
CPL Pubid: 187873