Approximate algorithms for graph clustering problem

DOI10.17223/20710410/45/7MaRDI QIDQ5151277zbMATH OpenOpenAlexFDO

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

Publication date 17 February 2021

Published in Prikladnaya Diskretnaya Matematika (Search for Journal in Brave)

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

zbMATH Keywords

approximation algorithmgraph clusteringperformance guarantee

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Recommendations

• A 2-approximation algorithm for the graph 2-clustering problem
• 2-approximation algorithms for two graph clustering problems
• Approximation algorithms for min-sum \(p\)-clustering
• scientific article; zbMATH DE number 7746258
• Graph clustering with a constraint on cluster sizes

Cites work

• A Local-Search 2-Approximation for 2-Correlation-Clustering
• Aggregating inconsistent information: ranking and clustering
• Approximation algorithms for graph approximation problems
• Cluster graph modification problems
• Clustering with qualitative information
• Computational complexity of the graph approximation problem
• Correlation clustering
• Correlation clustering with a fixed number of clusters
• Graph clustering
• scientific article; zbMATH DE number 53883 (Why is no real title available?)
• scientific article; zbMATH DE number 3482343 (Why is no real title available?)
• Near Optimal LP Rounding Algorithm for CorrelationClustering on Complete and Complete k-partite Graphs
• NP-hard problems in hierarchical-tree clustering
• Semi-supervised graph clustering: a kernel approach
• Short survey on graph correlation clustering with minimization criteria

Cited in

(6)

• Exact and approximation algorithms for clustering
• A 2-approximation algorithm for the graph 2-clustering problem
• Algorithms for Cluster Busting in Anchored Graph Drawing
• 2-approximation algorithms for two graph clustering problems
• ON GENERIC COMPLEXITY OF THE GRAPH CLUSTERING PROBLEM
• (Semi-)External Algorithms for Graph Partitioning and Clustering

This page was built for publication: Approximate algorithms for graph clustering problem

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