Nearly-perfect hypergraph packing is in NC |
| |
Authors: | David A. Grable |
| |
Affiliation: | Institut für Informatik, Humboldt-Universität zu Berlin, D-10099, Berlin, Germany |
| |
Abstract: | Answering a question of Rödl 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 run 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. |
| |
Keywords: | Algorithms Computational complexity |
本文献已被 ScienceDirect 等数据库收录! |
|