Structural parameterization of cluster deletion

DOI10.1007/S00453-025-01303-1MaRDI QIDQ6979988zbMATH OpenFDO

Authors Giuseppe F. Italiano, Athanasios L. Konstantinidis, Charis Papadopoulos

Publication date 23 May 2025

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/S00453-025-01303-1

zbMATH Keywords

cluster deletion problemFPT algorithmneighborhood diversitytwin cover numbervertex cover number

Mathematics Subject Classification ID

Signed and weighted graphs (05C22) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10)

Cites work

• Algorithmic meta-theorems for restrictions of treewidth
• Algorithms parameterized by vertex cover and modular width, through potential maximal cliques
• Alternative parameterizations for cluster editing
• An application of simultaneous diophantine approximation in combinatorial optimization
• Cluster deletion on interval graphs and split related graphs
• Cluster deletion revisited
• Cluster editing with locally bounded modifications
• Cluster editing: kernelization based on edge cuts
• Cluster graph modification problems
• Cluster vertex deletion: a parameterization between vertex cover and clique-width
• Complexity of the cluster deletion problem on subclasses of chordal graphs
• Correlation clustering
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Going weighted: parameterized algorithms for cluster editing
• scientific article; zbMATH DE number 6515825 (Why is no real title available?)
• scientific article; zbMATH DE number 2011849 (Why is no real title available?)
• scientific article; zbMATH DE number 7803591 (Why is no real title available?)
• Improved upper bounds for vertex cover
• Integer Programming with a Fixed Number of Variables
• Maximizing the strong triadic closure in split graphs and proper interval graphs
• Motif and Hypergraph Correlation Clustering
• On polynomial kernels for traveling salesperson problem and its generalizations
• On the approximate compressibility of connected vertex cover
• On the complexity of k-SAT
• On the relation of strong triadic closure and cluster deletion
• Parameterized algorithms
• Parameterized Algorithms for Modular-Width
• Preprocessing complexity for some graph problems parameterized by structural parameters
• Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations
• Structural parameterization of cluster deletion
• The cluster deletion problem for cographs
• The Complexity of Multiterminal Cuts
• The graph motif problem parameterized by the structure of the input graph
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Twin-Cover: Beyond Vertex Cover in Parameterized Algorithmics
• Twin-width and polynomial kernels
• Upper bounds to the clique width of graphs

Cited in

(2)

• When can cluster deletion with bounded weights be solved efficiently?
• Graph clustering problems under the Lens of parameterized local search

This page was built for publication: Structural parameterization of cluster deletion

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6979988)