A Heuristic Algorithm for Optimal Hamiltonian Cycles in Weighted Graphs

Authors

  • Tadeusz Ostrowski The Jacob of Paradyz University of Applied Sciences in Gorzow Wlkp.
  • Petroula Mavrikiou Frederick University, Nicosia

DOI:

https://doi.org/10.24297/jam.v11i6.1227

Keywords:

. Graph theory, Hamiltonian cycle, Payoff matrix

Abstract

Abstract. The paper focuses on finding of the optimal Hamiltonian cycle, when it is regarded with respect to cost, time, distance or difficulty level of the route. The problem is strictly related to the traveling salesman problem proved to be NP-complete for general graphs. The paper gives a heuristic algorithm for finding the optimal spanning cycle in a weighted graph. Its idea is based on optimization of weight losses and reduction the complexity of a problem by reduction the dimension of the graph payoff matrix. 

Downloads

Download data is not yet available.

Author Biography

Tadeusz Ostrowski, The Jacob of Paradyz University of Applied Sciences in Gorzow Wlkp.

Technical Department

Downloads

Published

2015-10-21

How to Cite

Ostrowski, T., & Mavrikiou, P. (2015). A Heuristic Algorithm for Optimal Hamiltonian Cycles in Weighted Graphs. JOURNAL OF ADVANCES IN MATHEMATICS, 11(6), 5300–5305. https://doi.org/10.24297/jam.v11i6.1227

Issue

Section

Articles