An improved fixed-parameter algorithm for 2-Club Cluster Edge Deletion

被引：2

作者：

Abu-Khzam, Faisal N. ^{[1
]}

Makarem, Norma ^{[1
]}

Shehab, Maryam ^{[1
]}

机构：

[1] Lebanese Amer Univ, Dept Comp Sci & Math, Beirut, Lebanon

来源：

THEORETICAL COMPUTER SCIENCE | 2023年 / 958卷

关键词：

Correlation clustering; 2-Club Cluster Edge Deletion; Cluster Editing; Fixed-parameter tractability;

D O I：

10.1016/j.tcs.2023.113864

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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.

引用

页数：8

共 23 条

[1] Cluster Editing with Vertex Splitting [J].

Abu-Khzam, Faisal N. ;

Egan, Judith ;

Gaspers, Serge ;

Shaw, Alexis ;

Shaw, Peter .

COMBINATORIAL OPTIMIZATION, ISCO 2018, 2018, 10856 :1-13

[2]

Abu-Khzam FN, 2017, J DISCRET ALGORITHMS, V45, P26, DOI 10.1016/j.jda.2017.07.003

[3]

Barr Joseph R., 2019, 2019 First International Conference on Graph Computing (GC), P29, DOI 10.1109/GC46384.2019.00013

[4] Vulnerability Rating of Source Code with Token Embedding and Combinatorial Algorithms [J].

Barr, Joseph R. ;

Shaw, Peter ;

Abu-Khzam, Faisal N. ;

Thatcher, Tyler ;

Yu, Sheng .

INTERNATIONAL JOURNAL OF SEMANTIC COMPUTING, 2020, 14 (04) :501-516

[5] Combinatorial Code Classification & Vulnerability Rating [J].

Barr, Joseph R. ;

Shaw, Peter ;

Abu-Khzam, Faisal N. ;

Yu, Sheng ;

Yin, Heng ;

Thatcher, Tyler .

2020 SECOND INTERNATIONAL CONFERENCE ON TRANSDISCIPLINARY AI (TRANSAI 2020), 2020, :80-83

[6]

Bocker Sebastian, 2013, The Nature of Computation. Logic, Algorithms, Applications. 9th Conference on Computability in Europe, CiE 2013. Proceedings: LNCS 7921, P33, DOI 10.1007/978-3-642-39053-1_5

[7] Exact Algorithms for Cluster Editing: Evaluation and Experiments [J].

Boecker, Sebastian ;

Briesemeister, Sebastian ;

Klau, Gunnar W. .

ALGORITHMICA, 2011, 60 (02) :316-334

[8] A modular computational framework for automated peak extraction from ion mobility spectra [J].

D'Addario, Marianna ;

Kopczynski, Dominik ;

Baumbach, Joerg Ingo ;

Rahmann, Sven .

BMC BIOINFORMATICS, 2014, 15

[9]

Dehne F, 2006, LECT NOTES COMPUT SC, V4169, P13

[10]

Fadiel A., 2006, AICCSA, V6, P8

← 1 2 3 →