$2$-Approximation algorithms for two graph clustering problems

DOI10.33048/daio.2020.27.680zbMath1491.68159OpenAlexW4240439807MaRDI QIDQ5090160

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 algorithmNP-hard problemgraph clusteringguaranteed approximation ratio

Mathematics Subject Classification ID

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

Related Items (1)

Experimental study of semi-supervised graph 2-clustering problem

Cites Work

• Unnamed Item
• Unnamed Item
• Correlation clustering
• Cluster graph modification problems
• Computational complexity of the graph approximation problem
• A Local-Search 2-Approximation for 2-Correlation-Clustering
• Approximating Symmetric Relations by Equivalence Relations

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