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

^*Tämän työn vastaava kirjoittaja

Information Theory

Tutkimustuotos: Lehtiartikkeli › Article › Scientific › vertaisarvioitu

1 Sitaatiot (Scopus)

79 Lataukset (Pure)

Abstrakti

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.

Alkuperäiskieli	Englanti
Sivut	527-546
Sivumäärä	20
Julkaisu	Journal of Combinatorial Designs
Vuosikerta	30
Numero	7
Varhainen verkossa julkaisun päivämäärä	18 huhtik. 2022
DOI - pysyväislinkit	https://doi.org/10.1002/jcd.21839
Tila	Julkaistu - heinäk. 2022
OKM-julkaisutyyppi	A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä

Pääsy asiakirjaan

10.1002/jcd.21839Lisenssi: CC BY

Algorithms and complexity for counting configurations in Steiner triple systemsFinal published version, 1,43 MBLisenssi: CC BY

Muut tiedostot ja linkit

Linkki julkaisuun Scopuksessa

Dataset for Algorithms and Complexity for Counting Configurations in Steiner Triple Systems
Heinlein, D. (Creator) & Östergård, P. (Creator), Zenodo, 2021
DOI - pysyväislinkki: 10.5281/zenodo.5519799
Tietoaineisto: Dataset

SubspaceCodes: Constructions and Classifications of Subspace Codes and Related Structures for Communication Networks
Heinlein, D. (Vastuullinen tutkija)
01/09/2020 → 31/08/2023
Projekti: Academy of Finland: Other research funding

Siteeraa tätä

@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

Abstrakti

Pääsy asiakirjaan

Muut tiedostot ja linkit

Sormenjälki

Tietoaineistot

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

Projektit

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

Siteeraa tätä