Algorithms and complexity for counting configurations in Steiner triple systems

Loading...
Thumbnail Image
Journal Title
Journal ISSN
Volume Title
A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä
Date
2022-07
Major/Subject
Mcode
Degree programme
Language
en
Pages
20
527-546
Series
Journal of Combinatorial Designs, Volume 30, issue 7
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