scientific article; zbMATH DE number 7278104

DOI10.4230/LIPIcs.FSTTCS.2017.32zbMath1493.05247arXiv1710.06339MaRDI QIDQ5136324

Guru Prashanth Guruganesh, Euiwoong Lee

Publication date: 25 November 2020

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

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

matchingsrandomized algorithmscontention resolution schemes

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Randomized algorithms (68W20)

Related Items (4)

Towards an optimal contention resolution scheme for matchings ⋮ Unnamed Item ⋮ A simple optimal contention resolution scheme for uniform matroids ⋮ An optimal monotone contention resolution scheme for bipartite matchings via a polyhedral viewpoint

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Price of Correlations in Stochastic Optimization
• Karp–Sipser on Random Graphs with a Fixed Degree Sequence
• Finding a maximum matching in a sparse random graph in O ( n ) expected time
• Perfect matchings in random bipartite graphs with minimal degree at least 2
• Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution Schemes
• On the existence of a factor of degree one of a connected random graph
• How to Sell Hyperedges: The Hypermatching Assignment Problem

This page was built for publication: