Radhakrishnan, Jaikumar (1992) Improved bounds for covering complete uniform hypergraphs Information Processing Letters, 41 (4). pp. 203-207. ISSN 0020-0190
Full text not available from this repository.
Official URL: http://www.sciencedirect.com/science/article/pii/0...
Related URL: http://dx.doi.org/10.1016/0020-0190(92)90181-T
Abstract
We consider the problem of covering the complete r-uniform hypergraphs on n vertices using complete r-partite graphs. We obtain lower bounds on the size of such a covering. For small values of r our result implies a lower bound of Ω( ( er/r √r)n log n) on the size of any such covering. This improves the previous bound of O(rn log n) due to Snir. We also obtain good lower bounds on the size of a family of perfect hash function using simple arguments.
| Item Type: | Article |
|---|---|
| Source: | Copyright of this article belongs to Elsevier Science. |
| Keywords: | Combinatorial Problems; Graph Covering; Perfect Hashing; Graph Entropy |
| ID Code: | 57643 |
| Deposited On: | 29 Aug 2011 08:35 |
| Last Modified: | 29 Aug 2011 08:35 |
Repository Staff Only: item control page
