期刊
THEORETICAL COMPUTER SCIENCE
卷 958, 期 -, 页码 -出版社
ELSEVIER
DOI: 10.1016/j.tcs.2023.113864
关键词
Correlation clustering; 2-Club Cluster Edge Deletion; Cluster Editing; Fixed-parameter tractability
A 2-club is a graph with diameter at most two. In the decision version of the 2-CLUB CLUSTER EDGE DELETION problem, it is asked whether an undirected graph G can be transformed into a disjoint union of 2-clubs by deleting at most k edges. This paper presents a fixed-parameter algorithm that breaks the 3k barrier and improves the previously claimed running time to O*(2.692k).
A 2-club is a graph of diameter at most two. In the decision version of the 2-CLUB CLUSTER EDGE DELETION problem, an undirected graph G is given along with an integer k >= 0 as parameter, and the question is whether G can be transformed into a disjoint union of 2-clubs by deleting at most k edges. A simple fixed-parameter algorithm solves the problem in O*(3k), and a decade-old algorithm improved this running to O*(2.74k) time via a more sophisticated case analysis. Unfortunately, this latter algorithm is shown to have a flawed branching scenario. A fixed-parameter algorithm that breaks the 3k barrier is presented in this paper, with a running time in O*(2.692k). This also improves the previously claimed running time. (c) 2023 Elsevier B.V. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据