A Heuristic Algorithm for Optimal Hamiltonian Cycles in Weighted Graphs
Journal Title: JOURNAL OF ADVANCES IN MATHEMATICS - Year 2015, Vol 11, Issue 6
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.
Authors and Affiliations
Tadeusz Ostrowski, Petroula Mavrikiou
Keywords
Related Articles
- EP ID EP651575
- DOI 10.24297/jam.v11i6.1227
- Views 137
- Downloads 0
A priori Estimate for the solution of Sylvester equation
For A, B and Y operators in B(H) it's well known the importance of sylvester equation AX - XB= Y in control theory and its applications. In this paper -using integral calculus- we were able to give a priori estimate of t...
The Total Open Monophonic Number of a Graph
For a connected graph G of order n >- 2, a subset S of vertices of G is a monophonic set of G if each vertex v in G lies on a x-y monophonic path for some elements x and y in S. The minimum cardinality of a monophonic...
Bounds on the finite-sample risk for exponential distribution.
In this paper, we derive lower and upper bounds on the expected nearest neighbor distance for exponential distribution, and find lower and upper bounds on the risk of the nearest neighbor of exponential distribution.
Generalized (; )-derivations and Left Ideals in Prime and Semiprime Rings
Let R be an associative ring, ; be the automorphisms of R, be a nonzero left ideal of R, F : R ! R be a generalized (; )-derivation and d : R ! Rbe an (; )-derivation. In the present paper we discuss the following situat...
Dual strongly Rickart modules
In this paper we introduce and study the concept of dual strongly Rickart modules as a stronger than of dual Rickart modules [8] and a dual concept of strongly Rickart modules. A module M is said to be dual strongly Rick...