Distributed half-integral matching and beyond

DOI10.1007/978-3-031-32733-9_15arXiv2303.05250OpenAlexW4377971762MaRDI QIDQ6148072

Sameep Dahal, Jukka Suomela

Publication date: 11 January 2024

Published in: Structural Information and Communication Complexity (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2303.05250

zbMATH Keywords

maximal matchingfractional matchingdistributed graph algorithmshalf-integral matching

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer system organization (68Mxx) Communication complexity, information complexity (68Q11)

Cites Work

• A fast and simple randomized parallel algorithm for maximal matching
• Linear-in-\(\varDelta \) lower bounds in the LOCAL model
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Improved deterministic distributed matching via rounding
• On the Distributed Complexity of Computing Maximal Matchings
• Distributed maximal matching
• Lower bounds for local approximation
• The Locality of Distributed Symmetry Breaking
• A Local 2-Approximation Algorithm for the Vertex Cover Problem
• A linear-time approximation algorithm for the weighted vertex cover problem
• A Lower Bound on Probabilistic Algorithms for Distributive Ring Coloring
• Locality in Distributed Graph Algorithms
• Distributed Computing: A Locality-Sensitive Approach
• Lower Bounds for Maximal Matchings and Maximal Independent Sets
• Some simple distributed algorithms for sparse networks

This page was built for publication: Distributed half-integral matching and beyond