A Linear Time Algorithm for Optimal Bottleneck Traveling Salesman Problem on a Halin Graph

被引：0

作者：

Lou, Dingjun ^{[1
]}

Dou, Hongke ^{[1
]}

机构：

[1] Sun Yat Sen Univ, Dept Comp Sci, Guangzhou 510275, Guangdong, Peoples R China

来源：

2011 INTERNATIONAL CONFERENCE ON COMPUTER, COMMUNICATION AND INFORMATION TECHNOLOGY (ICCCIT 2011) | 2011年

关键词：

Halin graph; linear time algorithm; optimal Hamilton cycle(path); bottleneck traveling salesman problem;

D O I：

暂无

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

Given a weighted graph H=(V, E), for each edge e is an element of E(H), e has a weight l(e) is an element of Z(+), and given a bound B is an element of Z(+). The optimal bottleneck traveling salesman problem (OBTSP) is to ask whether there is a Hamilton cycle C in H such that, for each e is an element of E(C), l(e) <= B, if there is such a cycle, then find the optimal such a cycle C and answer "Yes"; if there is not such a cycle, then answer "No". We design a linear time algorithm to solve OBTSP for weighted Halin graphs. At the end of this paper, we outline a method to design a linear time algorithm to find an optimal bottleneck Hamilton path between any. pair of vertices in a weighted Halin graph H.

引用

页码：60 / 62

页数：3