Algorithms and complexity for counting configurations in Steiner triple systems
Loading...
Access rights
openAccess
publishedVersion
URL
Journal Title
Journal ISSN
Volume Title
A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
Date
2022-07
Major/Subject
Mcode
Degree programme
Language
en
Pages
20
Series
Journal of Combinatorial Designs, Volume 30, issue 7, pp. 527-546
Abstract
Steiner triple systems form one of the most studied classes of combinatorial designs. Configurations, including subsystems, play a central role in the investigation of Steiner triple systems. With sporadic instances of small systems, ad hoc algorithms for counting or listing configurations are typically fast enough for practical needs, but with many systems or large systems, the relevance of computational complexity and algorithms of low complexity is highlighted. General theoretical results as well as specific practical algorithms for important configurations are presented.Description
Funding Information: The authors would like to thank the anonymous referees for their remarks, which improved the presentation of the results. Supported by the Academy of Finland, Grant No. 331044. Publisher Copyright: © 2022 The Authors. Journal of Combinatorial Designs published by Wiley Periodicals LLC.
Keywords
algorithm, computational complexity, configuration, Steiner triple system, subsystem
Other note
Citation
Heinlein, D & Östergård, P R J 2022, ' Algorithms and complexity for counting configurations in Steiner triple systems ', Journal of Combinatorial Designs, vol. 30, no. 7, pp. 527-546 . https://doi.org/10.1002/jcd.21839