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

MapReducedensest subgraph problemfractional maximum matching problem in bipartite graphs

Mathematics Subject Classification ID

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

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

• 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?)
• 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
• 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

(7)

• Brief announcement: MapReduce algorithms for massive trees
• The distributed algorithm for constructing extremal graphs without hexagon
• Locally computing edge orientations
• Sorting, searching, and simulation in the MapReduce framework
• Fractional set cover in the streaming model
• Distributed dense subgraph detection and low outdegree orientation
• On the generalized mean densest subgraph problem: complexity and algorithms

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)