Stručni rad

Computational Construction of Steiner Designs

Antonio Lakoš ; Sveučilište u Zagrebu, Fakultet elektrotehnike i računarstva, Zagreb *
Anamari Nakić ; Sveučilište u Zagrebu, Fakultet elektrotehnike i računarstva, Zagreb

* Dopisni autor.

Sažetak

A balanced incomplete block design, or simply a block design, with parameters (v, k, λ), consists of a finite set P of v points and a collection B of k-subsets of P (blocks), such that every pair of points is contained in exactly λ blocks. This paper describes the basic results on block designs. We show how the problem of constructing a block design can be modeled by means of a system of linear equations. Special attention is devoted to Steiner designs, that is, block designs for which λ = 1. We describe Algorithm X, introduced by the renowned mathematician and computer scientist Donald Knuth, for finding exact covers of a set,
as well as its application to the construction of Steiner designs. Finally, we demonstrate how block designs can be applied in planning research aimed at mitigating damage caused by climate change.

Ključne riječi

balanced incomplete block design, incidence matrix, Steiner design, Knuth’s Algorithm X

Hrčak ID:

340524

URI

https://hrcak.srce.hr/340524

Datum izdavanja:

1.6.2025.

Podaci na drugim jezicima: hrvatski

Posjeta: 316 *