Kernelization for Balanced Graph Clustering
Master thesis
Permanent lenke
https://hdl.handle.net/1956/24115Utgivelsesdato
2020-10-03Metadata
Vis full innførselSamlinger
- Master theses [220]
Sammendrag
The problems of Balanced Graph Clustering ask whether it is possible to modify a graph such that it becomes a cluster graph where no cluster has a size larger than a given multiplicative factor or absolute difference relative to any other cluster in the graph, by at most k graph modifications. In this thesis we study the problems with respect to the graph modification operations vertex deletion, edge addition and edge deletion. We will show NP-completeness and give polynomial kernels for each version.