IMPROVED BOUNDS FOR COVERING COMPLETE UNIFORM HYPERGRAPHS

被引：14

作者：

RADHAKRISHNAN, J ^{[1
]}

机构：

[1] RUTGERS STATE UNIV,DEPT COMP SCI,NEW BRUNSWICK,NJ 08903

来源：

INFORMATION PROCESSING LETTERS | 1992年 / 41卷 / 04期

关键词：

COMBINATORIAL PROBLEMS; GRAPH COVERING; PERFECT HASHING; GRAPH ENTROPY;

D O I：

10.1016/0020-0190(92)90181-T

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

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 OMEGA((e(r)/r square-root r)n log n) on the size of any such covering. This improves the previous bound of OMEGA(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.

引用

页码：203 / 207

页数：5