2-approximation algorithms for two graph clustering problems

DOI10.33048/DAIO.2020.27.680MaRDI QIDQ5090160zbMATH OpenOpenAlexFDO

Authors Alexander Morshinin, Victor Petrovich Il'ev, Svetlana Il'eva

Publication date 15 July 2022

Published in Diskretnyi analiz i issledovanie operatsii (Search for Journal in Brave)

Full work available at URL http://mathnet.ru/eng/da958

zbMATH Keywords

approximation algorithmgraph clusteringguaranteed approximation ratioNP-hard problem

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10) Learning and adaptive systems in artificial intelligence (68T05) Approximation algorithms (68W25)

Recommendations

• A 2-approximation algorithm for the graph 2-clustering problem
• An approximation algorithm for a semi-supervised graph clustering problem
• On a semi-supervised graph clustering problem
• Approximate algorithms for graph clustering problem
• scientific article; zbMATH DE number 1953109

Cites work

• A Local-Search 2-Approximation for 2-Correlation-Clustering
• Approximating Symmetric Relations by Equivalence Relations
• Cluster graph modification problems
• Computational complexity of the graph approximation problem
• Correlation clustering
• Correlation clustering with a fixed number of clusters
• scientific article; zbMATH DE number 3797792 (Why is no real title available?)

Cited in

(10)

• Exact algorithms for finding well-connected 2-clubs in sparse real-world graphs: theory and experiments
• A 2-approximation algorithm for the graph 2-clustering problem
• Approximating 2-cliques in unit disk graphs
• Exact algorithms for size constrained 2-clustering in the plane
• scientific article; zbMATH DE number 3902711 (Why is no real title available?)
• Approximation algorithms for approximating graphs with bounded number of connected components
• An approximation algorithm for a semi-supervised graph clustering problem
• On a semi-supervised graph clustering problem
• Approximate algorithms for graph clustering problem
• Experimental study of semi-supervised graph 2-clustering problem

This page was built for publication: 2-approximation algorithms for two graph clustering problems

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