Algorithms and complexity for counting configurations in Steiner triple systems

Daniel Heinlein; Patric R.J. Östergård

doi:10.1002/jcd.21839

Algorithms and complexity for counting configurations in Steiner triple systems

Daniel Heinlein^*, Patric R.J. Östergård

^*Corresponding author for this work

Information Theory

Research output: Contribution to journal › Article › Scientific › peer-review

32 Downloads (Pure)

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.

Original language	English
Pages (from-to)	527-546
Number of pages	20
Journal	Journal of Combinatorial Designs
Volume	30
Issue number	7
Early online date	18 Apr 2022
DOIs	https://doi.org/10.1002/jcd.21839
Publication status	Published - Jul 2022
MoE publication type	A1 Journal article-refereed

Keywords

algorithm
computational complexity
configuration
Steiner triple system
subsystem

Access to Document

10.1002/jcd.21839Licence: CC BY

Algorithms and complexity for counting configurations in Steiner triple systemsFinal published version, 1.43 MBLicence: CC BY

OpenUrl availability

Full text

Cite this

@article{118f770a21b847918006d298cbf98c16,

title = "Algorithms and complexity for counting configurations in Steiner triple systems",

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.",

keywords = "algorithm, computational complexity, configuration, Steiner triple system, subsystem",

author = "Daniel Heinlein and {\"O}sterg{\aa}rd, {Patric R.J.}",

note = "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: {\textcopyright} 2022 The Authors. Journal of Combinatorial Designs published by Wiley Periodicals LLC.",

year = "2022",

month = jul,

doi = "10.1002/jcd.21839",

language = "English",

volume = "30",

pages = "527--546",

journal = "Journal of Combinatorial Designs",

issn = "1063-8539",

publisher = "John Wiley & Sons",

number = "7",

}

TY - JOUR

T1 - Algorithms and complexity for counting configurations in Steiner triple systems

AU - Heinlein, Daniel

AU - Östergård, Patric R.J.

N1 - 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.

PY - 2022/7

Y1 - 2022/7

N2 - 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.

AB - 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.

KW - algorithm

KW - computational complexity

KW - configuration

KW - Steiner triple system

KW - subsystem

UR - http://www.scopus.com/inward/record.url?scp=85128323677&partnerID=8YFLogxK

U2 - 10.1002/jcd.21839

DO - 10.1002/jcd.21839

M3 - Article

AN - SCOPUS:85128323677

SN - 1063-8539

VL - 30

SP - 527

EP - 546

JO - Journal of Combinatorial Designs

JF - Journal of Combinatorial Designs

IS - 7

ER -

Algorithms and complexity for counting configurations in Steiner triple systems

Abstract

Keywords

Access to Document

OpenUrl availability

Other files and links

Fingerprint

Dataset for Algorithms and Complexity for Counting Configurations in Steiner Triple Systems

SubspaceCodes: Constructions and Classifications of Subspace Codes and Related Structures for Communication Networks

Cite this

Algorithms and complexity for counting configurations in Steiner triple systems

Abstract

Keywords

Access to Document

OpenUrl availability

Other files and links

Fingerprint

Datasets

Dataset for Algorithms and Complexity for Counting Configurations in Steiner Triple Systems

Projects

SubspaceCodes: Constructions and Classifications of Subspace Codes and Related Structures for Communication Networks

Cite this