dc.contributor.author | Steinvik, Andreas | |
dc.date.accessioned | 2020-10-03T08:30:33Z | |
dc.date.available | 2020-10-03T08:30:33Z | |
dc.date.issued | 2020-10-03 | |
dc.date.submitted | 2020-10-02T22:00:09Z | |
dc.identifier.uri | https://hdl.handle.net/1956/24115 | |
dc.description.abstract | 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. | |
dc.language.iso | eng | |
dc.publisher | The University of Bergen | |
dc.rights | Copyright the Author. All rights reserved | |
dc.subject | Clustering | |
dc.subject | Graphs | |
dc.subject | Kernelization | |
dc.subject | Algorithms | |
dc.subject | FPT | |
dc.title | Kernelization for Balanced Graph Clustering | |
dc.type | Master thesis | |
dc.date.updated | 2020-10-02T22:00:09Z | |
dc.rights.holder | Copyright the Author. All rights reserved | |
dc.description.degree | Masteroppgave i informatikk | |
dc.description.localcode | INF399 | |
dc.description.localcode | MAMN-INF | |
dc.description.localcode | MAMN-PROG | |
dc.subject.nus | 754199 | |
fs.subjectcode | INF399 | |
fs.unitcode | 12-12-0 | |