The multi-parameterized cluster editing problem

Faisal Abu Khzam

Research output: Chapter in Book/Report/Conference proceedingConference Paper published in ProceedingsResearchpeer-review

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 languageEnglish
Title of host publicationCombinatorial Optimization and Applications
EditorsPeter Widmayer, Xu Yinfeng, Zhu Binhai
Place of PublicationSwitzerland
PublisherSpringer
Pages284-294
Number of pages11
ISBN (Electronic)978-3-319-03780-6
ISBN (Print)978-3-319-03779-0
DOIs
Publication statusPublished - 2013
Externally publishedYes
EventConference on Combinatorial Optimization and Applications (COCOA 2013 7th) - Chengdu; China, Chengdu, China
Duration: 1 Jan 2013 → …
Conference number: 2013 (7th)

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume8287
ISSN (Print)0302-9743

Conference

ConferenceConference on Combinatorial Optimization and Applications (COCOA 2013 7th)
Abbreviated titleCOCOA
CountryChina
CityChengdu
Period1/01/13 → …

Fingerprint

Polynomials

Cite this

Abu Khzam, F. (2013). The multi-parameterized cluster editing problem. In P. Widmayer, X. Yinfeng, & Z. Binhai (Eds.), Combinatorial Optimization and Applications (pp. 284-294). (Lecture Notes in Computer Science; Vol. 8287). Switzerland: Springer. https://doi.org/10.1007/978-3-319-03780-6_25
Abu Khzam, Faisal. / The multi-parameterized cluster editing problem. Combinatorial Optimization and Applications. editor / Peter Widmayer ; Xu Yinfeng ; Zhu Binhai. Switzerland : Springer, 2013. pp. 284-294 (Lecture Notes in Computer Science).
@inproceedings{6dc40bb6f51747bcaa971729ace33904,
title = "The multi-parameterized cluster editing problem",
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.",
author = "{Abu Khzam}, Faisal",
year = "2013",
doi = "10.1007/978-3-319-03780-6_25",
language = "English",
isbn = "978-3-319-03779-0",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "284--294",
editor = "Peter Widmayer and Xu Yinfeng and Zhu Binhai",
booktitle = "Combinatorial Optimization and Applications",
address = "Switzerland",

}

Abu Khzam, F 2013, The multi-parameterized cluster editing problem. in P Widmayer, X Yinfeng & Z Binhai (eds), Combinatorial Optimization and Applications. Lecture Notes in Computer Science, vol. 8287, Springer, Switzerland, pp. 284-294, Conference on Combinatorial Optimization and Applications (COCOA 2013 7th), Chengdu, China, 1/01/13. https://doi.org/10.1007/978-3-319-03780-6_25

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 proceedingConference Paper published in ProceedingsResearchpeer-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 -

Abu Khzam F. The multi-parameterized cluster editing problem. In Widmayer P, Yinfeng X, Binhai Z, editors, Combinatorial Optimization and Applications. Switzerland: Springer. 2013. p. 284-294. (Lecture Notes in Computer Science). https://doi.org/10.1007/978-3-319-03780-6_25