Probabilistic analysis of the longest hamiltonian tour problem | Zendy

Vohra Rakesh V. | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Premium

Probabilistic analysis of the longest hamiltonian tour problem

Author(s) -

Vohra Rakesh V.

Publication year - 1988

Publication title -

networks

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.977

H-Index - 64

eISSN - 1097-0037

pISSN - 0028-3045

DOI - 10.1002/net.3230180103

Subject(s) - probabilistic logic , combinatorics , heuristic , hamiltonian (control theory) , mathematics , probabilistic analysis of algorithms , hamiltonian path , random graph , graph , enhanced data rates for gsm evolution , discrete mathematics , travelling salesman problem , computer science , mathematical optimization , statistics , artificial intelligence

In this paper we study the probabilistic behavior of the farthest neighbor heuristic for finding the longest Hamiltonian tour in a graph. We assume the edge weights are independent random variables uniformly distributed in [0,1]. If F, is the length of the heuristic tour and L, the optimal tour then F n /L n → 1 a.s. as n → α. We also show that L n /n → 1 a.s. as n → ∞.

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research