On the advantage of overlapping clusters for minimizing conductance

DOI10.1007/s00453-013-9761-8zbMath1303.05196OpenAlexW2026511931MaRDI QIDQ472486

Rohit Khandekar, Guy Kortsarz, Vahab S. Mirrokni

Publication date: 19 November 2014

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-013-9761-8

zbMATH Keywords

clusteringapproximationsocial networksconductance

Mathematics Subject Classification ID

Social networks; opinion dynamics (91D30) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items

Model selection strategies for determining the optimal number of overlapping clusters in additive overlapping partitional clustering ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Hearing the clusters of a graph: A distributed algorithm
• Primal-dual approximation algorithms for integral flow and multicut in trees
• An improved approximation algorithm of MULTIWAY CUT.
• Approximating directed multicuts
• Hardness of cut problems in directed graphs
• $O(\sqrt{\logn})$ Approximation to SPARSEST CUT in $\tilde{O}(n^2)$ Time
• Polynomial flow-cut gaps and hardness of directed cut problems
• Improved approximation for directed cut problems
• The importance of being biased
• Euclidean distortion and the sparsest cut
• Fast Approximate Graph Partitioning Algorithms
• Finding k Cuts within Twice the Optimal
• Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
• Clustering Social Networks
• Greedy approximation algorithms for directed multicuts
• Min-max Graph Partitioning and Small Set Expansion
• Graph partitioning using single commodity flows
• Expander flows, geometric embeddings and graph partitioning
• The dense \(k\)-subgraph problem

This page was built for publication: On the advantage of overlapping clusters for minimizing conductance