Multi-parameterized Cluster Editing
Project Description:
The Cluster Editing problem seeks a transformation of a given undirected graph
into a disjoint union of cliques via a (minimum) number of edge additions or
deletions. In this project, a multi-parameterized version of the problem is studied,
featuring a number of input parameters that bound the amount of both edge-additions and
deletions per single vertex, as well as the size of a clique-cluster.
We study the effect of multi-parameterization on the problem complexity as well as
some real applications. Parameters are chosen in an attempt to better-model
problems arising from application domains, especially Biology and Clinical research.
PI: Faisal N. Abu-Khzam
Funding: This project has been partially supported by the Lebanese
American University under grant SRDC-t2013-45.
Publications:
F. N. Abu-Khzam. The Multi-Parameterized Cluster Editing Problem,
in Proceedings of the 7th International Conference on Combinatorial
Optimization and Applications (COCOA 2013), Lecture Notes in Computer Science,
volume 8287, Chengdu, China, December 2013, pages 284-294.
F. N. Abu-Khzam. On the Complexity of Multi-Parameterized Cluster Editing
Journal of Discrete Algorithms, volume 45, pages 26-34, 2017.
F. N. Abu-Khzam, J. Egan, S. Gaspers, A. Shaw and P. Shaw.
Cluster Editing with Vertex Splitting,
in Proceedings of the 5th International Symposium on Combinatorial
Optimization (ISCO), Lecture Notes in Computer Science, volume 10856,
Marrakesh, Morroco, April 2018, pages 1-13.
J. R. Barr, P. Shaw, F. N. Abu-Khzam and J. Chen.
Combinatorial Text Classification:
the effect of multi-parameterized correlation clustering,
in Proceedings of the 1st
International Conference on Graph Computing (GC), IEEE, 2019: 29-36.