Home > Table of Contents

 

Proceedings of 2009 International Workshop on Information Security and Application (IWISA 2009)

Qingdao, China, November 21-22, 2009

Editors: Feng Gao and Xijun Zhu

AP Catalog Number: AP-PROC-CS-09CN004

ISBN: 978-952-5726-06-0

Page(s): 322-324

The NP-completeness of Completing Partial Anti-symmetric Latin Squares

Jiannan Chen

Full text: PDF

Abstract

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.

Index Terms

chromatic index, Latin squares, Latin background, anti- symmetric, NP-completeness

Copyright @ 2009 ACADEMY PUBLISHER All rights reserved