dc.contributor.author | Sunde, Joakim Hauger | |
dc.date.accessioned | 2023-01-26T00:55:35Z | |
dc.date.available | 2023-01-26T00:55:35Z | |
dc.date.issued | 2022-08-29 | |
dc.date.submitted | 2023-01-23T09:31:58Z | |
dc.identifier.uri | https://hdl.handle.net/11250/3046415 | |
dc.description.abstract | The problem of $\alpha-$ \textsl{BALANCED CLUSTER VERTEX DELETION} where \(\alpha \geq 1 \) is some constant, asks whether it is possible to delete at most \(k\) vertecies from a vertex colored graph such that that it becomes a cluster graph, where for each cluster, the ratios between the number of vertecies with each color is bounded by the constant \(\alpha \). We study the problem from a Parameterized Complexity point of view with the parameters \(k\) and \(l\), where \(k\) is the solution size and \(l\) is the number of colors. We present kernels with \(\mathcal{O}(k^2l)\) and \(\mathcal{O}(k^4) \) vertecies and an improved \(\mathcal{O}(k^3) \) kernel in the special case when \(\alpha = 1 \). We also provide an \(\mathcal{O}(3^k(|V|+|E|)) \) FTP algorithm. | |
dc.language.iso | eng | |
dc.publisher | The University of Bergen | |
dc.rights | Copyright the Author. All rights reserved | |
dc.subject | Cluster vertex deletion clustering parameterized complexity | |
dc.title | Parameterized Complexity of Fair Graph Clustering | |
dc.type | Master thesis | |
dc.date.updated | 2023-01-23T09:31:58Z | |
dc.rights.holder | Copyright the Author. All rights reserved | |
dc.description.degree | Masteroppgave i informatikk | |
dc.description.localcode | INF399 | |
dc.description.localcode | MAMN-PROG | |
dc.description.localcode | MAMN-INF | |
dc.subject.nus | 754199 | |
fs.subjectcode | INF399 | |
fs.unitcode | 12-12-0 | |