Towards optimal degree distributions for left-perfect matchings in random bipartite graphs

DOI10.1007/s00224-014-9577-1zbMath1317.05175arXiv1203.1506MaRDI QIDQ2354587

Martin Dietzfelbinger, Michael Rink

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

zbMATH Keywords

optimization; bipartite graph; matching; random graph; degree distribution; cuckoo hashing

Mathematics Subject Classification ID

05C80: Random graphs (graph-theoretic aspects)

60B20: Random matrices (probabilistic aspects)

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)