Graph partitioning using single commodity flows

DOI10.1145/1132516.1132574MaRDI QIDQ5891927zbMATH OpenOpenAlexFDO

Authors Rohit Khandekar, Satish Rao, Umesh V. Vazirani

Publication date 25 November 2014

Published in Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1132516.1132574

zbMATH Keywords

edge-separatorsingle commodity max-flowsparse cutspectral method

Mathematics Subject Classification ID

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

Recommendations

• Graph partitioning using single commodity flows
• \(O(\sqrt{\log n})\) approximation to sparsest cut in \(\tilde{O}(n^2)\) time
• Expander flows, geometric embeddings and graph partitioning
• Expander flows, geometric embeddings and graph partitioning
• Fast Approximate Graph Partitioning Algorithms

Cited in

(12)

• \(O(\sqrt{\log n})\) approximation to sparsest cut in \(\tilde{O}(n^2)\) time
• Algorithmic extensions of Cheeger's inequality to higher eigenvalues and partitions
• scientific article; zbMATH DE number 6501141 (Why is no real title available?)
• Fast Approximate Graph Partitioning Algorithms
• On the advantage of overlapping clusters for minimizing conductance
• Towards an SDP-based approach to spectral methods: a nearly-linear-time algorithm for graph partitioning and decomposition
• Fast C-K-R partitions of sparse graphs
• Approximate maximum flow on separable undirected graphs
• Expander flows, geometric embeddings and graph partitioning
• Graph partitioning using single commodity flows
• Expander flows, geometric embeddings and graph partitioning
• A simpler and parallelizable \(O(\sqrt{\log n})\)-approximation algorithm for \textsc{Sparsest Cut}

This page was built for publication: Graph partitioning using single commodity flows

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