DocumentCode
693508
Title
Parallelization of the dancing links algorithm
Author
Uelschen, Michael
Author_Institution
Fac. of Eng. & Comput. Sci., Univ. of Appl. Sci. Osnabruck, Osnabruck, Germany
fYear
2013
fDate
19-20 Dec. 2013
Firstpage
172
Lastpage
175
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;
fLanguage
English
Publisher
ieee
Conference_Titel
Information Management in the Knowledge Economy (IMKE), 2013 2nd International Conference on
Conference_Location
Chandigarh
Type
conf
Filename
6915093
Link To Document