Abstract
| 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 | China |
| City | Chengdu |
| Period | 1/01/13 → … |
Fingerprint
Cite this
}
The multi-parameterized cluster editing problem. / Abu Khzam, Faisal.
Combinatorial Optimization and Applications. ed. / Peter Widmayer; Xu Yinfeng; Zhu Binhai. Switzerland : Springer, 2013. p. 284-294 (Lecture Notes in Computer Science; Vol. 8287).Research output: Chapter in Book/Report/Conference proceeding › Conference Paper published in Proceedings › Research › peer-review
TY - GEN
T1 - The multi-parameterized cluster editing problem
AU - Abu Khzam, Faisal
PY - 2013
Y1 - 2013
N2 - 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.
AB - 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.
U2 - 10.1007/978-3-319-03780-6_25
DO - 10.1007/978-3-319-03780-6_25
M3 - Conference Paper published in Proceedings
SN - 978-3-319-03779-0
T3 - Lecture Notes in Computer Science
SP - 284
EP - 294
BT - Combinatorial Optimization and Applications
A2 - Widmayer, Peter
A2 - Yinfeng, Xu
A2 - Binhai, Zhu
PB - Springer
CY - Switzerland
ER -