Efficient primal-dual graph algorithms for MapReduce

DOI10.1007/978-3-319-13123-8_6zbMATH Open1342.05177OpenAlexW2126077878MaRDI QIDQ2945274FDOQ2945274

Bahman Bahmani, Kamesh Munagala, Ashish Goel

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• The multiplicative weights update method: a meta-algorithm and applications
• Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems
• Title not available (Why is that?)
• Linear Programming in the Semi-streaming Model with Application to the Maximum Matching Problem
• Title not available (Why is that?)
• Approximate minimum-cost multicommodity flows in \(\widetilde O(\varepsilon^{-2}KNM)\) time
• Fractional Matching Via Balls-and-Bins

Cited In (3)

• Fractional Set Cover in the Streaming Model.
• On the Locality of Nash-Williams Forest Decomposition and Star-Forest Decomposition
• Distributed dense subgraph detection and low outdegree orientation

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)