The multi-parameterized cluster editing problem
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 o...
Saved in:
| Main Author: | |
|---|---|
| Format: | conferenceObject |
| Published: |
2017
|
| Online Access: | http://hdl.handle.net/10725/5378 http://dx.doi.org/10.1007/978-3-319-03780-6_25 http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php https://link.springer.com/chapter/10.1007/978-3-319-03780-6_25 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1864513465858654208 |
|---|---|
| author | Abu-Khzam, Faisal N. |
| author_facet | Abu-Khzam, Faisal N. |
| author_role | author |
| dc.creator.none.fl_str_mv | Abu-Khzam, Faisal N. |
| dc.date.none.fl_str_mv | 2017-03-17T11:59:02Z 2017-03-17T11:59:02Z 2017-03-17 |
| dc.identifier.none.fl_str_mv | 978-3-319-03780-6 http://hdl.handle.net/10725/5378 http://dx.doi.org/10.1007/978-3-319-03780-6_25 Abu-Khzam, F. N. (2013). The multi-parameterized cluster editing problem. In Combinatorial Optimization and Applications (pp. 284-294). Springer International Publishing. http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php https://link.springer.com/chapter/10.1007/978-3-319-03780-6_25 |
| dc.language.none.fl_str_mv | en |
| dc.publisher.none.fl_str_mv | Springer |
| dc.rights.*.fl_str_mv | info:eu-repo/semantics/openAccess |
| dc.title.none.fl_str_mv | The multi-parameterized cluster editing problem Combinatorial Optimization and Applications |
| dc.type.none.fl_str_mv | Conference Paper / Proceeding info:eu-repo/semantics/publishedVersion info:eu-repo/semantics/conferenceObject |
| description | 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. |
| eu_rights_str_mv | openAccess |
| format | conferenceObject |
| id | LAURepo_c8a70627a267258818c47d039543bfa4 |
| identifier_str_mv | 978-3-319-03780-6 Abu-Khzam, F. N. (2013). The multi-parameterized cluster editing problem. In Combinatorial Optimization and Applications (pp. 284-294). Springer International Publishing. |
| language_invalid_str_mv | en |
| network_acronym_str | LAURepo |
| network_name_str | Lebanese American University repository |
| oai_identifier_str | oai:laur.lau.edu.lb:10725/5378 |
| publishDate | 2017 |
| publisher.none.fl_str_mv | Springer |
| repository.mail.fl_str_mv | |
| repository.name.fl_str_mv | |
| repository_id_str | |
| spelling | The multi-parameterized cluster editing problemCombinatorial Optimization and ApplicationsAbu-Khzam, Faisal N.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.N/ASpringer2017-03-17T11:59:02Z2017-03-17T11:59:02Z2017-03-17Conference Paper / Proceedinginfo:eu-repo/semantics/publishedVersioninfo:eu-repo/semantics/conferenceObject978-3-319-03780-6http://hdl.handle.net/10725/5378http://dx.doi.org/10.1007/978-3-319-03780-6_25Abu-Khzam, F. N. (2013). The multi-parameterized cluster editing problem. In Combinatorial Optimization and Applications (pp. 284-294). Springer International Publishing.http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.phphttps://link.springer.com/chapter/10.1007/978-3-319-03780-6_25eninfo:eu-repo/semantics/openAccessoai:laur.lau.edu.lb:10725/53782021-03-19T10:00:54Z |
| spellingShingle | The multi-parameterized cluster editing problem Abu-Khzam, Faisal N. |
| status_str | publishedVersion |
| title | The multi-parameterized cluster editing problem |
| title_full | The multi-parameterized cluster editing problem |
| title_fullStr | The multi-parameterized cluster editing problem |
| title_full_unstemmed | The multi-parameterized cluster editing problem |
| title_short | The multi-parameterized cluster editing problem |
| title_sort | The multi-parameterized cluster editing problem |
| url | http://hdl.handle.net/10725/5378 http://dx.doi.org/10.1007/978-3-319-03780-6_25 http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php https://link.springer.com/chapter/10.1007/978-3-319-03780-6_25 |