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 149
- Downloads 0
A way to compute a greatest common divisor in the Galois field (GF (2^n ))
This paper presents how the steps that used to determine a multiplicative inverse by method based on the Euclidean algorithm, can be used to find a greatest common divisor for polynomials in the Galois field (2^n ).
On Full k-ideals of a Ternary Semiring
In this paper, we generalize the concept of the full -ideals of a semiring to ternary semiring and prove that the set of zeroids annihilator of a right ternary semimodule, and the Jacobson radical of a ternary semiring a...
A Perishable Inventory System with Postponed Demands and Finite
In this article, we consider a continuous review perishable inventory system with a finite number of homogeneous sources generating demands. The demand time points form quasi random process and demand is for single item....
ANALYSIS OF NIGERIA GROSS DOMESTIC PRODUCT USING PRINCIPAL COMPONENT ANALYSIS
Nigeria is classified as a mixed economy emerging market, and has already reached middle income status according to the World Bank, with its abundant supply of natural resource, well developed financial, legal, communica...
A New Inexact Non-Interior Continuation Algorithm for Second-Order Cone Programming
Second-order cone programming has received considerable attention in the past decades because of its wide range of applications. Non-interior continuation method is one of the most popular and efficient methods for solvi...