文章基本信息

标题：Clustering to Given Connectivities
本地全文：下载
作者：Petr A. Golovach ; Dimitrios M. Thilikos
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2019
卷号：148
页码：1-17
DOI：10.4230/LIPIcs.IPEC.2019.18
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We define a general variant of the graph clustering problem where the criterion of density for the clusters is (high) connectivity. In Clustering to Given Connectivities, we are given an n-vertex graph G, an integer k, and a sequence Lambda= of positive integers and we ask whether it is possible to remove at most k edges from G such that the resulting connected components are exactly t and their corresponding edge connectivities are lower-bounded by the numbers in Lambda. We prove that this problem, parameterized by k, is fixed parameter tractable, i.e., can be solved by an f(k)* n^{O(1)}-step algorithm, for some function f that depends only on the parameter k. Our algorithm uses the recursive understanding technique that is especially adapted so to deal with the fact that we do not impose any restriction to the connectivity demands in Lambda.
关键词：graph clustering; edge connectivity; parameterized complexity