The multi-parameterized cluster editing problem

LAUR Repository

Show simple item record

dc.contributor.author Abu-Khzam, Faisal N.
dc.date.accessioned 2017-03-17T11:59:02Z
dc.date.available 2017-03-17T11:59:02Z
dc.identifier.isbn 978-3-319-03780-6 en_US
dc.identifier.uri http://hdl.handle.net/10725/5378
dc.description.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. en_US
dc.language.iso en en_US
dc.publisher Springer en_US
dc.title The multi-parameterized cluster editing problem en_US
dc.type Conference Paper / Proceeding en_US
dc.author.school SAS en_US
dc.author.idnumber 200302941 en_US
dc.author.department Computer Science and Mathematics en_US
dc.description.embargo N/A en_US
dc.identifier.doi http://dx.doi.org/10.1007/978-3-319-03780-6_25 en_US
dc.identifier.ctation Abu-Khzam, F. N. (2013). The multi-parameterized cluster editing problem. In Combinatorial Optimization and Applications (pp. 284-294). Springer International Publishing. en_US
dc.author.email faisal.abukhzam@lau.edu.lb en_US
dc.conference.date December 12-14, 2013 en_US
dc.conference.pages 284-294 en_US
dc.conference.place Chengdu, China en_US
dc.conference.title 7th International Conference, COCOA 2013 en_US
dc.identifier.tou http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php en_US
dc.identifier.url https://link.springer.com/chapter/10.1007/978-3-319-03780-6_25 en_US
dc.author.affiliation Lebanese American University en_US
dc.title.volume Combinatorial Optimization and Applications en_US

Files in this item

This item appears in the following Collection(s)

Show simple item record

Search LAUR

Advanced Search


My Account