On the complexity of certain completion problems

MaRDI QIDQ2716514zbMATH OpenFDO

Authors R. G. Parker, S. Horton, T. Easton

Publication date 2 January 2002

Published in Congressus Numerantium (Search for Journal in Brave)

zbMATH Keywords

completion problemsLatin squarelinear arrangementNP-complete

Mathematics Subject Classification ID

Orthogonal arrays, Latin squares, Room squares (05B15) Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• On completing latin squares
• The complexity of completing partial Latin squares
• Some completion problems for graphs without chordless cycles of prescribed lengths
• scientific article; zbMATH DE number 3873343
• Completing colored graphs to meet a target property

Cited in

(10)

• On some algorithmic problems regarding the hairpin completion
• Shellings from relative shellings, with an application to NP-completeness
• The Complexity of theA B CProblem
• System Completion Problem: Theory and Applications
• Computing and Combinatorics
• On Some $\mathcal{NP}$ -complete SEFE Problems
• scientific article; zbMATH DE number 7535772 (Why is no real title available?)
• Exploring the complexity boundary between coloring and list-coloring
• A series of algorithmic results related to the iterated hairpin completion
• A finite set of functions with an EXPTIME-complete composition problem

This page was built for publication: On the complexity of certain completion problems

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