NEARLY-PERFECT HYPERGRAPH PACKING IS IN NC

Authors
GRABLE DA
Citation
Da. Grable, NEARLY-PERFECT HYPERGRAPH PACKING IS IN NC, Information processing letters, 60(6), 1996, pp. 295-299
Citations number
17
Categorie Soggetti
Information Science & Library Science","Computer Science Information Systems
Journal title
Information processing letters → ACNP
ISSN journal
00200190
Volume
60
Issue
6
Year of publication
1996
Pages
295 - 299
Database
ISI
SICI code
0020-0190(1996)60:6<295:NHPIIN>2.0.ZU;2-F
Abstract
Answering a question of Rodl and Thoma, we show that the Nibble Algori thm for finding a collection of disjoint edges covering almost all ver tices in an almost regular, uniform hypergraph with negligible pair de grees can be derandomized and parallelized to run in polylog time on p olynomially many parallel processors. In other words, the nearly-perfe ct packing problem on this class of hypergraphs is in the complexity c lass NC.