Efficient primal-dual graph algorithms for MapReduce

DOI10.1007/978-3-319-13123-8_6MaRDI QIDQ2945274zbMATH OpenOpenAlexFDO

Authors Bahman Bahmani, Ashish Goel, Kamesh Munagala

Publication date 9 September 2015

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-13123-8_6

zbMATH Keywords

densest subgraph problemfractional maximum matching problem in bipartite graphsMapReduce

Mathematics Subject Classification ID

Density (toughness, etc.) (05C42) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• scientific article; zbMATH DE number 6297759
• Brief announcement: MapReduce algorithms for massive trees
• Round compression for parallel matching algorithms
• Sorting, searching, and simulation in the MapReduce framework
• Round compression for parallel matching algorithms

Cites work

• Approximate minimum-cost multicommodity flows in \(\widetilde O(\varepsilon^{-2}KNM)\) time
• Distributed algorithms for multicommodity flow problems via approximate steepest descent framework
• Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems
• Fractional Matching Via Balls-and-Bins
• scientific article; zbMATH DE number 1670532 (Why is no real title available?)
• scientific article; zbMATH DE number 910872 (Why is no real title available?)
• scientific article; zbMATH DE number 6297759 (Why is no real title available?)
• Linear programming in the semi-streaming model with application to the maximum matching problem
• The multiplicative weights update method: a meta-algorithm and applications

Cited in

(9)

• The distributed algorithm for constructing extremal graphs without hexagon
• Sorting, searching, and simulation in the MapReduce framework
• Fractional set cover in the streaming model
• Brief announcement: MapReduce algorithms for massive trees
• Distributed dense subgraph detection and low outdegree orientation
• On the generalized mean densest subgraph problem: complexity and algorithms
• Locally computing edge orientations
• Approximating densest subgraph in geometric intersection graphs
• Near-optimal differentially private graph algorithms via the multidimensional abovethreshold mechanism

This page was built for publication: Efficient primal-dual graph algorithms for MapReduce

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