Title :
Parallelization of the dancing links algorithm
Author :
Uelschen, Michael
Author_Institution :
Fac. of Eng. & Comput. Sci., Univ. of Appl. Sci. Osnabruck, Osnabruck, Germany
Abstract :
In this paper we provide a parallel formulation of the dancing links algorithm described by Donald E. Knuth. This algorithm uses an efficient encoding of the exact set cover problem. Using backtracking the state space is search in a depth-first manner. We will derive the parallel algorithm and outline some implementation details. We conclude with experimental results for the n-queens-problem showing the nearly linear speed-up of the presented approach.
Keywords :
backtracking; parallel algorithms; backtracking; dancing links algorithm; exact set cover problem; n-queens-problem; parallel algorithm; parallel formulation; parallelization; Algorithm design and analysis; Arrays; Finite element analysis; Instruction sets; Parallel algorithms; Partitioning algorithms; backtracking; exact set covering; parallel algorithm;
Conference_Titel :
Information Management in the Knowledge Economy (IMKE), 2013 2nd International Conference on
Conference_Location :
Chandigarh
