\((1,1)\)-cluster editing is polynomial-time solvable

DOI10.1016/j.dam.2023.07.002zbMath1521.05199arXiv2210.07722OpenAlexW4385400757MaRDI QIDQ6048436

Gregory Gutin, Anders Yeo

Publication date: 14 September 2023

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2210.07722

zbMATH Keywords

polynomial algorithmcluster editing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• A \(2k\) kernel for the cluster editing problem
• Exact algorithms for cluster editing: Evaluation and experiments
• Cluster editing with locally bounded modifications
• Graph-modeled data clustering: Exact algorithms for clique generation
• A more effective linear kernelization for cluster editing
• Going weighted: parameterized algorithms for cluster editing
• NP-hard problems in hierarchical-tree clustering
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Cluster editing: kernelization based on edge cuts
• Cluster graph modification problems
• A golden ratio parameterized algorithm for cluster editing
• On the complexity of multi-parameterized cluster editing

This page was built for publication: \((1,1)\)-cluster editing is polynomial-time solvable