The complexity of completing partial Latin squares

DOI10.1016/0166-218X(84)90075-1zbMATH Open0538.05013OpenAlexW2083140445WikidataQ55880491 ScholiaQ55880491MaRDI QIDQ793029FDOQ793029

Authors: Charles J. Colbourn 

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

Recommendations

• scientific article; zbMATH DE number 1556753
• On the completability of incomplete Latin squares
• scientific article; zbMATH DE number 2170410
• scientific article; zbMATH DE number 3887704
• Constrained completion of partial Latin squares
• Completions of \(\epsilon \)-dense partial Latin squares
• scientific article; zbMATH DE number 2170449
• On Completing Latin Squares
• scientific article; zbMATH DE number 1529466

zbMATH Keywords

NP-completepartial Latin squarespartitioning tripartite graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Orthogonal arrays, Latin squares, Room squares (05B15) Graph theory (05C99)

Cites Work

• Graph theory
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• On Representatives of Subsets
• Title not available (Why is that?)
• A Combinatorial Theorem with an Application to Latin Rectangles
• Distinct representatives of subsets
• The NP-Completeness of Some Edge-Partition Problems
• Systems of Distinct Representations and Linear Programming
• Title not available (Why is that?)
• Title not available (Why is that?)
• Embedding partial Steiner triple systems is NP-complete
• Title not available (Why is that?)

Cited In (51)

• An improved approximation algorithm for the partial Latin square extension problem.
• Completion of partial Latin hypercube designs: NP-completeness and inapproximability
• On the completability of incomplete orthogonal Latin rectangles
• Estimating the number of Latin rectangles by the fast simulation method
• Exploring the complexity boundary between coloring and list-coloring
• Problems from CGCS Luminy, May 2007
• A note on the hardness of Skolem-type sequences
• Title not available (Why is that?)
• Constructing and embedding mutually orthogonal Latin squares: reviewing both new and existing results
• Cropper's question and Cruse's theorem about partial Latin squares
• Completing partial Latin squares with one nonempty row, column, and symbol
• List-edge-colouring planar graphs with precoloured edges
• The fewest clues problem
• Avoiding and extending partial edge colorings of hypercubes
• On the completability of incomplete Latin squares
• The Sudoku completion problem with rectangular hole pattern is NP-complete
• On completing latin squares
• A census of critical sets based on non-trivial autotopisms of Latin squares of order up to five
• Complexity of token swapping and its variants
• Completing partial commutative quasigroups constructed from partial Steiner triple systems is NP-complete
• The power of propagation: when GAC is enough
• An effective greedy heuristic for the social golfer problem
• An improved SAT formulation for the social golfer problem
• Computing random \(r\)-orthogonal Latin squares
• Characterization of extreme points of multi-stochastic tensors
• Title not available (Why is that?)
• Title not available (Why is that?)
• The complexity of constructing gerechte designs
• Exploring the complexity boundary between coloring and list-coloring
• Approximating latin square extensions
• On NP-hardness of the clique partition -- independence number gap recognition and related problems
• A Latin square autotopism secret sharing scheme
• On avoiding some families of arrays
• List edge multicoloring in graphs with few cycles
• Completion and deficiency problems
• A randomized tabu search-based approach for perfect stranger matching in economic experiments
• A Bayesian approach to tackling hard computational problems. (Preliminary report)
• Consensus models: computational complexity aspects in modern approaches to the list coloring problem
• Exact sampling algorithms for Latin squares and Sudoku matrices via probabilistic divide-and-conquer
• Multigraph realizations of degree sequences: Maximization is easy, minimization is hard
• A new algorithm for enumerating all possible Sudoku squares
• Randomized post-optimization of covering arrays
• Triangulations of 3-way regular tripartite graphs of degree 4, with applications to orthogonal latin squares
• A massively parallel evolutionary algorithm for the partial Latin square extension problem
• Extension of some edge graph problems: standard, parameterized and approximation complexity
• A characterization of odd-hole inequalities related to Latin squares
• Reliable assignments of processors to tasks and factoring on matroids
• Flexibility of triangle‐free planar graphs
• On the complexity of certain completion problems
• Restricted completion of sparse partial Latin squares
• Iterated local search with Trellis-neighborhood for the partial Latin square extension problem

This page was built for publication: The complexity of completing partial Latin squares

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q793029)