Towards optimal degree distributions for left-perfect matchings in random bipartite graphs
From MaRDI portal
Publication:2354587
DOI10.1007/s00224-014-9577-1zbMath1317.05175arXiv1203.1506OpenAlexW101522598MaRDI QIDQ2354587
Michael Rink, Martin Dietzfelbinger
Publication date: 20 July 2015
Published in: Theory of Computing Systems, Computer Science – Theory and Applications (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1203.1506
Random graphs (graph-theoretic aspects) (05C80) Random matrices (probabilistic aspects) (60B20) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cites Work
- Space efficient hash tables with worst case constant access time
- Mixed Hypergraphs for Linear-Time Construction of Denser Hashing-Based Data Structures
- Sharp load thresholds for cuckoo hashing
- Maximum matchings in random bipartite graphs and the space utilization of Cuckoo Hash tables
- Tight Thresholds for Cuckoo Hashing via XORSAT
- Efficient erasure correcting codes
- Concentration of Measure for the Analysis of Randomized Algorithms