The complexity of completing partial Latin squares
From MaRDI portal
Publication:793029
DOI10.1016/0166-218X(84)90075-1zbMath0538.05013OpenAlexW2083140445WikidataQ55880491 ScholiaQ55880491MaRDI QIDQ793029
Publication date: 1984
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0166-218x(84)90075-1
Analysis of algorithms and problem complexity (68Q25) Orthogonal arrays, Latin squares, Room squares (05B15) Graph theory (05C99)
Related Items (43)
On the completability of incomplete orthogonal Latin rectangles ⋮ Avoiding and extending partial edge colorings of hypercubes ⋮ List-edge-colouring planar graphs with precoloured edges ⋮ Completing partial Latin squares with one nonempty row, column, and symbol ⋮ The fewest clues problem ⋮ A census of critical sets based on non-trivial autotopisms of Latin squares of order up to five ⋮ On NP-hardness of the clique partition -- independence number gap recognition and related problems ⋮ Characterization of extreme points of multi-stochastic tensors ⋮ A Latin square autotopism secret sharing scheme ⋮ A new algorithm for enumerating all possible Sudoku squares ⋮ Triangulations of 3-way regular tripartite graphs of degree 4, with applications to orthogonal latin squares ⋮ Unnamed Item ⋮ A randomized tabu search-based approach for perfect stranger matching in economic experiments ⋮ Exact sampling algorithms for Latin squares and Sudoku matrices via probabilistic divide-and-conquer ⋮ Extension of some edge graph problems: standard, parameterized and approximation complexity ⋮ Flexibility of triangle‐free planar graphs ⋮ A massively parallel evolutionary algorithm for the partial Latin square extension problem ⋮ Completion and deficiency problems ⋮ The power of propagation: when GAC is enough ⋮ Consensus models: computational complexity aspects in modern approaches to the list coloring problem ⋮ Exploring the complexity boundary between coloring and list-coloring ⋮ Exploring the complexity boundary between coloring and list-coloring ⋮ Completion of partial Latin hypercube designs: NP-completeness and inapproximability ⋮ Reliable assignments of processors to tasks and factoring on matroids ⋮ Multigraph realizations of degree sequences: Maximization is easy, minimization is hard ⋮ Approximating latin square extensions ⋮ Iterated local search with Trellis-neighborhood for the partial Latin square extension problem ⋮ Randomized post-optimization of covering arrays ⋮ On the completability of incomplete Latin squares ⋮ Problems from CGCS Luminy, May 2007 ⋮ An effective greedy heuristic for the social golfer problem ⋮ An improved SAT formulation for the social golfer problem ⋮ A note on the hardness of Skolem-type sequences ⋮ An improved approximation algorithm for the partial Latin square extension problem. ⋮ Complexity of token swapping and its variants ⋮ Cropper's question and Cruse's theorem about partial Latin squares ⋮ Restricted completion of sparse partial Latin squares ⋮ List edge multicoloring in graphs with few cycles ⋮ On avoiding some families of arrays ⋮ Estimating the number of Latin rectangles by the fast simulation method ⋮ Completing partial commutative quasigroups constructed from partial Steiner triple systems is NP-complete ⋮ Constructing and embedding mutually orthogonal Latin squares: reviewing both new and existing results ⋮ A characterization of odd-hole inequalities related to Latin squares
Cites Work
- Embedding partial Steiner triple systems is NP-complete
- Systems of Distinct Representations and Linear Programming
- The NP-Completeness of Some Edge-Partition Problems
- On Representatives of Subsets
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- Distinct representatives of subsets
- A Combinatorial Theorem with an Application to Latin Rectangles
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: The complexity of completing partial Latin squares
