Journal
THEORETICAL COMPUTER SCIENCE
Volume 984, Issue -, Pages -Publisher
ELSEVIER
DOI: 10.1016/j.tcs.2023.114321
Keywords
Algorithms; Graph algorithms; Cluster deletion problem; Parameterized complexity; Automated generation of branching rules
Categories
Ask authors/readers for more resources
This paper proposes algorithms for 2-CLUB CLUSTER VERTEX DELETION and 2-CLUB CLUSTER EDGE DELETION problems. The algorithms have running times of O*(3.104k) and O*(2.562k) respectively, and were obtained using automated generation of branching rules. These results improve upon previous algorithms for the same problems.
In the 2-CLUB CLUSTER VERTEX DELETION (resp., 2-CLUB CLUSTER EDGE DELETION) problem the input is a graph G and an integer k, and the goal is to decide whether there is a set of at most k vertices (resp., edges) whose removal from G results in a graph in which the diameter of every connected component is at most 2. In this paper we give algorithms for 2-CLUB CLUSTER VERTEX DELETION and 2-CLUB CLUSTER EDGE DELETION whose running times are O*(3.104k) and O*(2.562k), respectively. Our algorithms were obtained using automated generation of branching rules. Our results improve the previous O*(3.303k)-time algorithm for 2-CLUB CLUSTER VERTEX DELETION [Liu et al., FAW-AAIM 2012] and the O*(2.695k)-time algorithm for 2-CLUB CLUSTER EDGE DELETION [Abu-Khzam et al., TCS 2023].
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available