Fast Distributed Approximation Algorithm for the Maximum Matching Problem in Bounded Arboricity Graphs

No abstract is available for this paper.

• Publication year

  2009

• Venue

  International Symposium on Algorithms and Computation

• Publication date

  2009-12-05

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1007/978-3-642-10631-6_68
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Deterministic Coin Tossing with Applications to Optimal Parallel List Ranking

  2018cited by this paper
• Algorithms and Computational Complexity

  2014cited by this paper
• Fast Distributed Approximations in Planar Graphs

  2008cited by this paper
• Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition

  2008cited by this paper
• The price of being near-sighted

  2006cited by this paper
• Distributed Approximation Algorithms for Planar Graphs

  2006cited by this paper
• Distributed Approximation Algorithms in Unit-Disk Graphs

  2006cited by this paper
• Fast Deterministic Distributed Maximal Independent Set Computation on Growth-Bounded Graphs

  2005cited by this paper
• Local approximation schemes for ad hoc and sensor networks

  2005cited by this paper
• Distributed approximation: a survey

  2004cited by this paper
• Distributed algorithm for approximating the maximum matching

  2004cited by this paper
• Distributed Algorithm for Better Approximation of the Maximum Matching

  2003cited by this paper
• Constant-time distributed dominating set approximation

  2003cited by this paper
• Some simple distributed algorithms for sparse networks

  2001cited by this paper
• Graph Theory

  1997cited by this paper
• On the distributed complexity of computing maximal matchings

  1997cited by this paper
• A Fast and Simple Randomized Parallel Algorithm for Maximal Matching

  1986cited by this paper
• A n^5/2 Algorithm for Maximum Matchings in Bipartite Graphs

  1971cited by this paper

• Improved Deterministic Distributed Maximum Weight Independent Set Approximation in Sparse Graphs

  2024cites this paper
• (1 − (cid:15) )-Approximate Maximum Weighted Matching in poly(1 /(cid:15), log n ) Time in the Distributed and Parallel Settings

  2023cites this paper
• $(1-\epsilon)$-Approximate Maximum Weighted Matching in Distributed, Parallel, and Semi-Streaming Settings

  2022cites this paper
• Differential Privacy from Locally Adjustable Graph Algorithms: k-Core Decomposition, Low Out-Degree Ordering, and Densest Subgraphs

  2022cites this paper
• Simple Combinatorial Algorithms for the Minimum Dominating Set Problem in Bounded Arboricity Graphs

  2021cites this paper
• Algorithms for the Minimum Dominating Set Problem in Bounded Arboricity Graphs: Simpler, Faster, and Combinatorial

  2021cites this paper
• Local Algorithms for Bounded Degree Sparsifiers in Sparse Graphs

  2021influential citation
• Bibliography of distributed approximation on structurally sparse graph classes

  2020cites this paper
• An estimator for matching size in low arboricity graphs with two applications

  2020cites this paper
• Bibliography of distributed approximation beyond bounded degree

  2020cites this paper
• Massive Graph Analysis in the Data Stream Model

  2019cites this paper
• Distributed Local Approximation Algorithms for Maximum Matching in Graphs and Hypergraphs

  2018cites this paper
• Structural Results on Matching Estimation with Applications to Streaming

  2018cites this paper
• Distributed Alarming in the On-Duty and Off-Duty Models

  2016cites this paper
• Planar Matching in Streams Revisited

  2016cites this paper
• On graph algorithms for large-scale graphs

  2015cites this paper
• Distributed algorithms for random graphs

  2015cites this paper
• Sublinear Estimation of Weighted Matchings in Dynamic Data Streams

  2015cites this paper
• Distributed graph coloring in a few rounds

  2011cites this paper