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

Nearly-perfect hypergraph packing is in NC

โœ Scribed by David A. Grable

Book ID
104137305
Publisher
Elsevier Science
Year
1996
Tongue
English
Weight
477 KB
Volume
60
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

โœฆ Synopsis

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 parallel processors. In other words, the nearly-perfect packing problem on this class of hypergraphs is in the complexity class NC.

๐Ÿ“œ SIMILAR VOLUMES

New bounds on nearly perfect matchings i
New bounds on nearly perfect matchings in hypergraphs: Higher codegrees do help
โœ Van H. Vu ๐Ÿ“‚ Article ๐Ÿ“… 2000 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 253 KB

Let H be a k + 1 -uniform, D-regular hypergraph on n vertices and let H be the minimum number of vertices left uncovered by a matching in H. C j H , the j-codegree of H, is the maximum number of edges sharing a set of j vertices in common. We prove a general upper bound on H , based on the codegree