Applications of combinatorial designs in computer science
- 1 June 1989
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Computing Surveys
- Vol. 21 (2) , 223-250
- https://doi.org/10.1145/66443.66446
Abstract
The theory of combinatorial designs has been used in widely different areas of computation concerned with the design and analysis of both algorithms and hardware. Combinatorial designs capture a subtle balancing property that is inherent in many difficult problems and hence can provide a sophisticated tool for addressing these problems. The role of combinatorial designs in solving many problems that are basic to the field of computing is explored in this paper. Case studies of many applications of designs to computation are given; these constitute a first survey, which provides a representative sample of uses of designs. More importantly, they suggest paradigms in which designs can be used profitably in algorithm design and analysis.Keywords
This publication has 48 references indexed in Scilit:
- On splitting sets in block designs and finding roots of polynomialsDiscrete Mathematics, 1990
- On a Packing and Covering ProblemEuropean Journal of Combinatorics, 1985
- Embedding partial steiner triple systems is NP-completeJournal of Combinatorial Theory, Series A, 1983
- Hashing and trie algorithms for partial match retrievalACM Transactions on Database Systems, 1976
- Partial match retrievalBIT Numerical Mathematics, 1976
- A conversion algorithm for logarithms on GF(2n)Journal of Pure and Applied Algebra, 1974
- Some partitions of all triples into steiner triple systemsPublished by Springer Nature ,1974
- An existence theory for pairwise balanced designs II. The structure of PBD-closed sets and the existence conjecturesJournal of Combinatorial Theory, Series A, 1972
- An existence theory for pairwise balanced designs I. Composition theorems and morphismsJournal of Combinatorial Theory, Series A, 1972
- Factoring polynomials over large finite fieldsMathematics of Computation, 1970