Distributed sparse cut approximation

DOI10.4230/LIPICS.OPODIS.2015.10MaRDI QIDQ5363801zbMATH OpenOpenAlexFDO

Authors Fabian Kuhn, Anisur Rahaman Molla

Publication date 29 September 2017

Full work available at URL http://dx.doi.org/10.4230/LIPIcs.OPODIS.2015.10

zbMATH Keywords

all-prefix-sumsconductancerandom walkssparsest cut

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Recommendations

• Almost-Tight Distributed Minimum Cut Algorithms
• Distributed minimum cut approximation
• Congested Clique Algorithms for the Minimum Cut Problem
• Fast Distributed Computation of Cuts Via Random Circulations
• Near-optimal distributed maximum flow (extended abstract)

Cited in

(6)

• Distributed minimum cut approximation
• Sparse Cut Projections in Graph Streams
• Smaller Cuts, Higher Lower Bounds
• Improved distributed expander decomposition and nearly optimal triangle enumeration
• Almost-Tight Distributed Minimum Cut Algorithms
• A simpler and parallelizable \(O(\sqrt{\log n})\)-approximation algorithm for \textsc{Sparsest Cut}

This page was built for publication: Distributed sparse cut approximation

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