Graph partitioning using single commodity flows

DOI10.1145/1538902.1538903MaRDI QIDQ5899510zbMATH OpenOpenAlexFDO

Authors Rohit Khandekar, Satish Rao, Umesh V. Vazirani

Publication date 11 November 2015

Published in Journal of the ACM (Search for Journal in Brave)

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

zbMATH Keywords

edge-separatorsingle commodity MAX-flowsparse cutspectral method

Mathematics Subject Classification ID

Flows in graphs (05C21) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Deterministic network models in operations research (90B10) Programming involving graphs or networks (90C35)

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

(32)

• Towards tight(er) bounds for the excluded grid theorem
• Routing in undirected graphs with constant congestion
• \(O(\sqrt{\log n})\) approximation to sparsest cut in \(\tilde{O}(n^2)\) time
• Planar Digraphs
• scientific article; zbMATH DE number 6501141 (Why is no real title available?)
• Minimum-cost network design with (dis)economies of scale
• Fast Approximate Graph Partitioning Algorithms
• Constant congestion routing of symmetric demands in planar directed graphs
• Compact oblivious routing
• Local flow partitioning for faster edge connectivity
• Hallucination helps: energy efficient virtual circuit routing
• Approximate maximum flow on separable undirected graphs
• Compact oblivious routing in weighted graphs
• Flow-Based Algorithms for Improving Clusters: A Unifying Framework, Software, and Performance
• Graph partitioning using single commodity flows
• Expander flows, geometric embeddings and graph partitioning
• Expander flows, geometric embeddings and graph partitioning
• Constant Congestion Brambles
• Fission: Practical algorithms for computing minimum balanced node separators
• An Escape Time Formulation for Subgraph Detection and Partitioning of Directed Graphs
• A new deterministic algorithm for fully dynamic all-pairs shortest paths
• On the size of two minimal linkages
• Better decremental and fully dynamic sensitivity oracles for subgraph connectivity
• Approximate cut \& packing ratios for multi-commodity arborescences
• Maximum flow and minimum-cost flow in almost-linear time
• Deterministic expander routing: faster and more versatile
• Deterministic minimum Steiner cut in maximum flow time
• Practical expander decomposition
• A Cheeger inequality for size-specific conductance
• Near-optimal directed low-diameter decompositions
• Submodular hypergraph partitioning: metric relaxations and fast algorithms via an improved cut-matching game
• Near-optimal algorithm for directed expander decompositions

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 Q5899510)