The NP-completeness of Completing Partial anti-symmetric Latin squares

摘要：

This paper shows that deciding whether a partial anti-symmetric Latin square can be completed is NP complete. It imitates the proof of J.Colbourn 2 and exhibits a polynomial reduction from the known NP-complete problem which is called edge-colouring problem of regular graph.

关键词： chromatic index Latin squares Latin background anti-symmetric NP-completeness

作者: Chen Jian nan

作者单位: Computer School, National University of Defense Technology, Changsha, China

会议类型: 国际会议

会议名称: 2009 International Workshop on Information Security and Application(2009 信息安全与应用国际研讨会)

会议地点: 青岛

会议语种:英文

页码: 322-324

在线出版日期: 2009-11-21（万方平台首次上网日期，不代表论文的发表时间）