Back to Search
Start Over
Algorithms for 2-club cluster deletion problems using automated generation of branching rules.
- Source :
-
Theoretical Computer Science . Feb2024, Vol. 984, pN.PAG-N.PAG. 1p. - Publication Year :
- 2024
-
Abstract
- 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.104 k) and O ⁎ (2.562 k) , respectively. Our algorithms were obtained using automated generation of branching rules. Our results improve the previous O ⁎ (3.303 k) -time algorithm for 2-Club Cluster Vertex Deletion [Liu et al., FAW-AAIM 2012] and the O ⁎ (2.695 k) -time algorithm for 2-Club Cluster Edge Deletion [Abu-Khzam et al., TCS 2023]. [ABSTRACT FROM AUTHOR]
- Subjects :
- *ALGORITHMS
*GRAPH algorithms
*DIAMETER
Subjects
Details
- Language :
- English
- ISSN :
- 03043975
- Volume :
- 984
- Database :
- Academic Search Index
- Journal :
- Theoretical Computer Science
- Publication Type :
- Academic Journal
- Accession number :
- 174447593
- Full Text :
- https://doi.org/10.1016/j.tcs.2023.114321