Embedding partial Steiner triple systems is NP-complete

DOI10.1016/0097-3165(83)90031-6zbMath0529.68020OpenAlexW1969129067MaRDI QIDQ787671

Charles J. Colbourn

Publication date: 1983

Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0097-3165(83)90031-6

zbMATH Keywords

partial Steiner triple systempartial commutative quasigroup

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial aspects of block designs (05B05) Loops, quasigroups (20N05)

Related Items

Some NP-complete problems for hypergraph degree sequences ⋮ Existence and embeddings of partial Steiner triple systems of order ten with cubic leaves ⋮ Quadratic leaves of maximal partial triple systems ⋮ The impact of search heuristics on heavy-tailed behaviour ⋮ The strong chromatic number of partial triple systems ⋮ Triangulations of 3-way regular tripartite graphs of degree 4, with applications to orthogonal latin squares ⋮ Small Embeddings of Partial Steiner Triple Systems ⋮ Solving non-Boolean satisfiability problems with stochastic local search: A comparison of encodings ⋮ \textsc{Conjure}: automatic generation of constraint models from problem specifications ⋮ On determining when small embeddings of partial Steiner triple systems exist ⋮ On a class of completable partial edge-colourings ⋮ Algorithm portfolios ⋮ Embeddings of partial Steiner triple systems ⋮ Completing partial commutative quasigroups constructed from partial Steiner triple systems is NP-complete ⋮ Completing small partial triple systems ⋮ The complexity of completing partial Latin squares ⋮ Small embeddings of partial directed triple systems and partial triple systems with even \(\lambda\) ⋮ An Evans-Style Result for Block Designs

Cites Work

• Premature sets of 1-factors or how not to schedule round robin tournaments
• Completing small partial triple systems
• On embedding incomplete symmetric Latin squares
• The completion of finite incomplete Steiner triple systems with applications to loop theory
• A Survey of Embedding Theorems for Steiner Systems
• Embedding Partial Steiner Triple Systems
• The NP-Completeness of Some Edge-Partition Problems
• The NP-Completeness of Edge-Coloring
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Systems of Distinct Representatives
• Unnamed Item

This page was built for publication: Embedding partial Steiner triple systems is NP-complete