Communications - Scientific Letters of the University of Zilina 2009, 11(3):15-19 | DOI: 10.26552/com.C.2009.3.15-19

Parallel Backtracking Algorithm for Hamiltonian Path Search

Karol Grondzak1, Penka Martincova1
1 Department of Informatics, Faculty of Management Science and Informatics, University of Zilina, Slovakia

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.

Keywords: no keywords

Published: September 30, 2009  Show citation

ACS AIP APA ASA Harvard Chicago Chicago Notes IEEE ISO690 MLA NLM Turabian Vancouver
Grondzak, K., & Martincova, P. (2009). Parallel Backtracking Algorithm for Hamiltonian Path Search. Communications - Scientific Letters of the University of Zilina, 11(3), 15-19. doi: 10.26552/com.C.2009.3.15-19
Share...
Download citation
  • BibTeX (.bib)
  • Bookends (.ris)
  • EasyBib (.ris)
  • EndNote (.enw)
  • EndNote 8 (.xml)
  • ISI WoS (.isi)
  • Medlars (.medlars)
  • Mendeley (.ris)
  • MODS (.xml)
  • Papers (.ris)
  • RefWorks (.txt)
  • RefManager (.ris)
  • RIS (.ris)
  • MS Word (.xml)
  • Zotero (.ris)
    • Open full article

    References

    1. GENDRON, B., CRAINIC, T. G.: Parallel Branch and Bound Algorithms: Survey and Synthesis, Operations Research, 42, pp. 1042-1066, 1994. Go to original source...
    2. CRAINIC, T. G., LE CUN, B., ROUCAIROL, C.: Parallel Branch-and-Bound Algorithms, Wiley Interscience, October 2006, ch. 1. Go to original source...
    3. MEZMAZ, M., MELAB, N., TALBI, E-G.: A Grid-enabled Branch and Bound Algorithm for Solving Challenging Combinatorial Optimization Problems, In Proc. of 21st IEEE Intl. Parallel and Distributed Processing Symp., Long Beach, California, 2007. Go to original source...
    4. QUINN, M. J.: Parallel Programming in C with MPI and OpenMP. Mc Graw Hill, 2003. ISBN 007-123265-6.
    5. WILKINSON, B., ALLEN, M.: Parallel Programming Second Edition. Pearson Education, 2005. ISBN: 0-13-140563-2.
    6. KUCERA, L.: Combinatorial algorithms (in Slovak), SNTL, 1989.
    7. NAGESHWARA RAO, V., KUMAR, V.: On the Efficiency of Parallel Backtracking, IEEE Trans. Parallel Distrib. Syst. 4(4): 427-437 (1993). Go to original source...
    8. http://www.open-mpi.org/
    9. GROPP, W., LUSK, E., SKJELLUM, A.: Using MPI, Second Edition. The MIT Press, 1999. ISBN: 978-0-262-57134-0. Go to original source...
    10. KVASNICA, I., KVASNICA, P., IGAZOVA, M.: Parallel Modeling in Computer Systems, Acta Avionica, Vol. X, 2008, 16. ISSN 1335-9479, pp. 8-86.
    11. SCHMIDT, M. C., SAMATOVA, N. F., THOMAS K, PARK, B. H.: A scalable, parallel algorithm for maximal clique enumeration, J. Parallel Distrib. Comput. 69 (2009), pp. 417-428. Go to original source...
    12. GRONDZAK, K., MARTINCOVA, P., CHOCHLIK, M.: Performance Analysis of Parallel Algorithm for Backtracking, Proc. of 4th International Workshop on Grid Computing for Complex Problems, Bratislava, 2008.

    This is an open access article distributed under the terms of the Creative Commons Attribution 4.0 International License (CC BY 4.0), which permits use, distribution, and reproduction in any medium, provided the original publication is properly cited. No use, distribution or reproduction is permitted which does not comply with these terms.


    Return to the content