Distributed half-integral matching and beyond

DOI10.1016/j.tcs.2023.114278OpenAlexW4388091301MaRDI QIDQ6199402

Jukka Suomela, Sameep Dahal

Publication date: 23 February 2024

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2023.114278

zbMATH Keywords

computational complexitymaximal matchingfractional matchingdistributed graph algorithms

Mathematics Subject Classification ID

Theory of computing (68Qxx)

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
• What Can be Computed Locally?
• 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