๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Constructing a perfect matching is in random NC

โœ Scribed by R. M. Karp; E. Upfal; A. Wigderson

Book ID
110564449
Publisher
Springer-Verlag
Year
1986
Tongue
English
Weight
759 KB
Volume
6
Category
Article
ISSN
0209-9683

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

Nearly-perfect hypergraph packing is in
Nearly-perfect hypergraph packing is in NC
โœ David A. Grable ๐Ÿ“‚ Article ๐Ÿ“… 1996 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 477 KB

Answering a question of Rod1 and Thoma, we show that the Nibble Algorithm for finding a collection of disjoint edges covering almost all vertices in an almost regular, uniform hypergraph with negligible pair degrees can be derandomized and parallelized to mn in polylog time on polynomially many para

Perfect fractional matchings in random h
Perfect fractional matchings in random hypergraphs
โœ Michael Krivelevich ๐Ÿ“‚ Article ๐Ÿ“… 1996 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 890 KB

Given an r-uniform hypergraph H = (V, E ) on ( V ( = n vertices, a real-valued function f(e) 5 1 for all u E V and C e E E f(e) = n/r. Considering a random r-uniform hypergraph process of n vertices, we show that with probability tending to 1 as n + m , at the very moment to when the last isolated