Abstract
The Cluster Editing problem seeks a transformation of a
given undirected graph into a transitive graph via a minimum number of
edge-edit operations. Existing algorithms often exhibit slow performance
and could deliver clusters of no practical significance, such as singletons.
A constrained version of Cluster Editing is introduced, featuring more
input parameters that set a lower bound on the size of a clique-cluster
as well as upper bounds on the amount of both edge-additions and deletions
per vertex. The new formulation allows us to solve Cluster Editing
(exactly) in polynomial time when edge-edit operations per vertex is
smaller than half the minimum cluster size. Moreover, we address the
case where the new edge addition and deletion bounds (per vertex) are
small constants. We show that Cluster Editing has a linear-size kernel in
this case.
| Original language | English |
|---|---|
| Title of host publication | Combinatorial Optimization and Applications |
| Editors | Peter Widmayer, Xu Yinfeng, Zhu Binhai |
| Place of Publication | Switzerland |
| Publisher | Springer |
| Pages | 284-294 |
| Number of pages | 11 |
| ISBN (Electronic) | 978-3-319-03780-6 |
| ISBN (Print) | 978-3-319-03779-0 |
| DOIs | |
| Publication status | Published - 2013 |
| Externally published | Yes |
| Event | Conference on Combinatorial Optimization and Applications (COCOA 2013 7th) - Chengdu; China, Chengdu, China Duration: 1 Jan 2013 → … Conference number: 2013 (7th) |
Publication series
| Name | Lecture Notes in Computer Science |
|---|---|
| Publisher | Springer |
| Volume | 8287 |
| ISSN (Print) | 0302-9743 |
Conference
| Conference | Conference on Combinatorial Optimization and Applications (COCOA 2013 7th) |
|---|---|
| Abbreviated title | COCOA |
| Country/Territory | China |
| City | Chengdu |
| Period | 1/01/13 → … |