Distributed half-integral matching and beyond

DOI10.1016/J.TCS.2023.114278MaRDI QIDQ6199402zbMATH OpenOpenAlexFDO

Authors Sameep Dahal, Jukka Suomela

Publication date 23 February 2024

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

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

computational complexitydistributed graph algorithmsfractional matchingmaximal matching

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• A fast and simple randomized parallel algorithm for maximal matching
• A linear-time approximation algorithm for the weighted vertex cover problem
• A Local 2-Approximation Algorithm for the Vertex Cover Problem
• A Lower Bound on Probabilistic Algorithms for Distributive Ring Coloring
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Distributed Computing: A Locality-Sensitive Approach
• Distributed maximal matching, greedy is optimal
• Improved deterministic distributed matching via rounding
• Linear-in- lower bounds in the LOCAL model
• Locality in Distributed Graph Algorithms
• Lower Bounds for Maximal Matchings and Maximal Independent Sets
• On the distributed complexity of computing maximal matchings
• Some simple distributed algorithms for sparse networks
• The locality of distributed symmetry breaking
• What Can be Computed Locally?

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6199402)