| dc.contributor | 資科系 | en_US |
| dc.creator (作者) | 連耀南 | zh_TW |
| dc.creator (作者) | Lien,Yao-Nan;Ma,Eva;Wah,Benjamin W.-S. | en_US |
| dc.date (日期) | 1993-10 | en_US |
| dc.date.accessioned | 28-Aug-2014 10:43:58 (UTC+8) | - |
| dc.date.available | 28-Aug-2014 10:43:58 (UTC+8) | - |
| dc.date.issued (上傳時間) | 28-Aug-2014 10:43:58 (UTC+8) | - |
| dc.identifier.uri (URI) | http://nccur.lib.nccu.edu.tw/handle/140.119/69392 | - |
| dc.description.abstract (摘要) | In the generalized traveling-salesman problem (GTSP), we are given a set of cities that are grouped into possibly intersecting clusters. The objective is to find a closed path of minimum cost that visits at least one city in each cluster. Given an instance G of the GTSP, we first transform G into another instance G′ of the GTSP in which all the clusters are nonintersecting, and then transform G′ into an instance G″ of the standard traveling-salesman problem (TSP). We show that any feasible solution of the TSP instance G″ can be transformed into a feasible solution of the GTSP instance G of no greater cost, and that any optimal solution of the TSP instance G″ can be transformed into an optimal solution of the GTSP instance G. | en_US |
| dc.format.extent | 1294247 bytes | - |
| dc.format.mimetype | application/pdf | - |
| dc.language.iso | en_US | - |
| dc.relation (關聯) | Information Sciences,74, (1-2),177-189 | en_US |
| dc.title (題名) | Transformation of the generalized traveling-salesman problem into the standard traveling-salesman problem | en_US |
| dc.type (資料類型) | article | en |
| dc.identifier.doi (DOI) | 10.1016/0020-0255(93)90133-7 | en_US |
| dc.doi.uri (DOI) | http://dx.doi.org/10.1016/0020-0255(93)90133-7 | en_US |
