Cutting up is hard to do: the parameterised complexity of k-Cut and related problems
Mostra el registre complet Registre parcial de l'ítem
- dc.contributor.author Downey, Rodney G.
- dc.contributor.author Estivill-Castro, V. (Vladimir)
- dc.contributor.author Fellows, Michael
- dc.contributor.author Prieto, Elena
- dc.contributor.author Rosamund, Frances A.
- dc.date.accessioned 2019-02-06T17:27:13Z
- dc.date.available 2019-02-06T17:27:13Z
- dc.date.issued 2003
- dc.description.abstract The Graph k-Cut problem is that of finding a set of edges of minimum total weight, in an edge-weighted graph, such that their removal from the graph results in a graph having at least k connected components. An algorithm with a running time of O(nk2) for this problem has been known since 1988, due to Goldschmidt and Hochbaum. We show that the problem is hard for the parameterized complexity class W[1]. We also investigate the complexity of a related problem, Cutting A Few Vertices from a Graph, that asks for the minimum cost of separating at least k vertices from an edge-weighted connected graph. We show that this problem also is hard for W[1].en
- dc.format.mimetype application/pdf
- dc.identifier.citation Downey RG, Estivill-Castro V, Fellows M, Prieto E, Rosamund FA. Cutting up is hard to do: the parameterised complexity of k-Cut and related problems. Electron Notes Theor Comput Sci. 2003 Apr;78:209-22. DOI: 10.1016/S1571-0661(04)81014-4
- dc.identifier.doi http://dx.doi.org/10.1016/S1571-0661(04)81014-4
- dc.identifier.issn 1571-0661
- dc.identifier.uri http://hdl.handle.net/10230/36518
- dc.language.iso eng
- dc.publisher Elsevier
- dc.relation.ispartof Electronic Notes in Theoretical Computer Science. 2003 Apr;78:209-22.
- dc.rights © Elsevier http://dx.doi.org/10.1016/S1571-0661(04)81014-4
- dc.rights.accessRights info:eu-repo/semantics/openAccess
- dc.title Cutting up is hard to do: the parameterised complexity of k-Cut and related problems
- dc.type info:eu-repo/semantics/article
- dc.type.version info:eu-repo/semantics/submittedVersion