Hall's Condition for Partial Latin Squares

Details Hall's Condition for Partial Latin Squares Hall's Condition for Partial Latin Squares

2011-07-13

arxiv.org/abs/1107.2639v1

Mathematics

Combinatorics

23 pages; 9 figures

Scientific paper

Hall's Condition is a necessary condition for a partial latin square to be completable. Hilton and Johnson showed that for a partial latin square whose filled cells form a rectangle, Hall's Condition is equivalent to Ryser's Condition, which is a necessary and sufficient condition for completability. We give what could be regarded as an extension of Ryser's Theorem, by showing that for a partial latin square whose filled cells form a rectangle, where there is at most one empty cell in each column of the rectangle, Hall's Condition is a necessary and sufficient condition for completability. It is well-known that the problem of deciding whether a partial latin square is completable is NP-complete. We show that the problem of deciding whether a partial latin square that is promised to satisfy Hall's Condition is completable is NP-hard.

Affiliated with

Also associated with

No associations

Rating

Hall's Condition for Partial Latin Squares does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Hall's Condition for Partial Latin Squares, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hall's Condition for Partial Latin Squares will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-166453