Friday 25th March talk by Abdullah about application of Bipartite Matching in completing partially filled Latin Square

[Abdullah Al Mahmud]

Hello,
This Friday we can refresh some of our ideas from Combinatorics and Graph
Theory.

I will discuss about the complexity of completing a partially filled Latin
Square(http://en.wikipedia.org/wiki/Latin_square ).

Our initial problem will be to complete a variation of incomplete Latin
Square where each row is either complete or empty. We will show that by
applying Hall's Marriage Theorem
(http://en.wikipedia.org/wiki/Hall%27s_marriage_theorem) and Bipartite
Matching algorithm we can solve this problem in Polynomial time. We will
focus on some graph theory ideas while discussing this problem.

And Finally we will prove that the complexity of filling any incomplete
Latin Square is NP-Complete. We will follow the proof from this paper
http://dx.doi.org/10.1016%2F0166-218X%2884%2990075-1

Thanks & Regards,
satej