Efficient Primal-Dual Graph Algorithms for MapReduce

DOI10.1007/978-3-319-13123-8_6zbMath1342.05177OpenAlexW2126077878MaRDI QIDQ2945274

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

zbMATH Keywords

MapReducedensest subgraph problemfractional maximum matching problem in bipartite graphs

Mathematics Subject Classification ID

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

Related Items (2)

On the Locality of Nash-Williams Forest Decomposition and Star-Forest Decomposition ⋮ Fractional Set Cover in the Streaming Model.

Cites Work

• Approximate minimum-cost multicommodity flows in \(\widetilde O(\varepsilon^{-2}KNM)\) time
• Linear Programming in the Semi-streaming Model with Application to the Maximum Matching Problem
• Fractional Matching Via Balls-and-Bins
• Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Efficient Primal-Dual Graph Algorithms for MapReduce