首页   按字顺浏览 期刊浏览 卷期浏览 Probabilistic analysis of the longest hamiltonian tour problem
Probabilistic analysis of the longest hamiltonian tour problem

 

作者: Rakesh V. Vohra,  

 

期刊: Networks  （WILEY Available online 1988）
卷期: Volume 18, issue 1  

页码: 13-18

 

ISSN:0028-3045

 

年代: 1988

 

DOI:10.1002/net.3230180103

 

出版商: Wiley Subscription Services, Inc., A Wiley Company

 

数据来源: WILEY

 

摘要:

AbstractIn 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 Fn/Ln→ 1 a.s. as n → α. We also show that Ln/n → 1 a.s. as

 

点击下载:  PDF (230KB)



返 回