𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Distance-2-Matchings of Random Graphs

✍ Scribed by C. M. Reidys

Publisher
Springer
Year
2004
Tongue
English
Weight
202 KB
Volume
8
Category
Article
ISSN
0218-0006

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Random Matchings in Regular Graphs
Random Matchings in Regular Graphs
✍ Jeff Kahn; Jeong Han Kim πŸ“‚ Article πŸ“… 1998 πŸ› Springer-Verlag 🌐 English βš– 339 KB
Small maximal matchings in random graphs
Small maximal matchings in random graphs
✍ Michele Zito πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 204 KB

We look at the minimal size of a maximal matching in general, bipartite and d-regular random graphs. We prove that with high probability the ratio between the sizes of any two maximal matchings approaches one in dense random graphs and random bipartite graphs. Weaker bounds hold for sparse random gr

Small maximal matchings of random cubic
Small maximal matchings of random cubic graphs
✍ H. Assiyatun; W. Duckworth πŸ“‚ Article πŸ“… 2009 πŸ› John Wiley and Sons 🌐 English βš– 330 KB

## Abstract We consider the expected size of a smallest maximal matching of cubic graphs. Firstly, we present a randomized greedy algorithm for finding a small maximal matching of cubic graphs. We analyze the average‐case performance of this heuristic on random __n__‐vertex cubic graphs using diffe