Parallel backtracking algorithm for hamiltonian path search

被引：0

作者：

Grondzak, Karol ^{[1
]}

Martincova, Penka ^{[1
]}

机构：

[1] Department of Informatics, Faculty of Management Science and Informatics, University of Zilina

来源：

Communications - Scientific Letters of the University of Žilina | 2009年 / 11卷 / 03期

关键词：

Hamiltonians - Optimization algorithms - Parallel algorithms;

D O I：

10.26552/com.c.2009.3.15-19

中图分类号：

学科分类号：

摘要：

The speed of calculations is a common problem to tackle in many areas of scientific research and real life. This paper presents an implementation of a parallel backtracking algorithm. The performance of the proposed algorithm is demonstrated on the problem of Hamiltonian Path search. Obtained results exhibit significant improvement of the parallel algorithm over the sequential one. Different aspects of parallelization of backtracking algorithm are studied and presented.

引用

页码：15 / 19

页数：4

共 11 条

[1]

Gendron B., Crainic T.G., Parallel branch and bound algorithms: Survey and synthesis, Operations Research, 42, pp. 1042-1066, (1994)

[2]

Crainic T.G., Le Cun B., Roucairol C., Parallel Branch-and-Bound Algorithms, (2006)

[3]

Mezmaz M., Melab N., Talbi E-G., A grid-enabled branch and bound algorithm for solving challenging combinatorial optimization problems, Proc. of 21st IEEE Intl. Parallel and Distributed Processing Symp., (2007)

[4]

Quinn M.J., Parallel Programming in C with MPI and OpenMP, (2003)

[5]

Wilkinson B., Allen M., Parallel Programming Second Edition, (2005)

[6]

Kucera L., Combinatorial Algorithms (in Slovak), (1989)

[7]

Nageshwara R.V., Kumar V., On the efficiency of parallel backtracking, IEEE Trans. Parallel Distrib. Syst., 4, 4, pp. 427-437, (1993)

[8]

Gropp W., Lusk E., Skjellum A., Using MPI, (1999)

[9]

Kvasnica I., Kvasnica P., Igazova M., Parallel Modeling in Computer Systems, 10, pp. 8-86, (2008)

[10]

Schmidt M.C., Samatova N.F., Thomas K, Park B.H., A scalable, parallel algorithm for maximal clique enumeration, J. Parallel Distrib. Comput., 69, pp. 417-428, (2009)

← 1 2 →