Algorithms and complexity for counting configurations in Steiner triple systems

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

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

3 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 languageEnglish
Pages (from-to)527-546
Number of pages20
JournalJournal of Combinatorial Designs
Volume30
Issue number7
Early online date18 Apr 2022
DOIs
Publication statusPublished - Jul 2022
MoE publication typeA1 Journal article-refereed

Keywords

  • algorithm
  • computational complexity
  • configuration
  • Steiner triple system
  • subsystem

Fingerprint

Dive into the research topics of 'Algorithms and complexity for counting configurations in Steiner triple systems'. Together they form a unique fingerprint.

Cite this