Algorithms and complexity for counting configurations in Steiner triple systems
Loading...
Access rights
openAccess
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
View/Open full text file from the Research portal
Other link related to publication
View publication in the Research portal
View/Open full text file from the Research portal
Other link related to publication
Date
2022-07
Department
Major/Subject
Mcode
Degree programme
Language
en
Pages
20
527-546
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
