2016年2月
An Improved Exact Algorithm for TSP in Graphs of Maximum Degree 4
THEORY OF COMPUTING SYSTEMS
- ,
- 巻
- 58
- 号
- 2
- 開始ページ
- 241
- 終了ページ
- 272
- 記述言語
- 英語
- 掲載種別
- 研究論文（学術雑誌）
- DOI
- 10.1007/s00224-015-9612-x
- 出版者・発行元
- SPRINGER
The paper presents a 1.692(n)n(O(1))-time polynomial-space algorithm for the traveling salesman problem in an n-vertex edge-weighted graph with maximum degree 4, which improves the previous results of the 1.890(n)n(O(1))-time polynomial-space algorithm by Eppstein and the 1.733(n)n(O(1))-time exponential-space algorithm by Gebauer.
- リンク情報
-
- DOI
- https://doi.org/10.1007/s00224-015-9612-x
- DBLP
- https://dblp.uni-trier.de/rec/journals/mst/XiaoN16
- J-GLOBAL
- https://jglobal.jst.go.jp/detail?JGLOBAL_ID=201702201270738826
- Web of Science
- https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=JSTA_CEL&SrcApp=J_Gate_JST&DestLinkType=FullRecord&KeyUT=WOS:000373747200002&DestApp=WOS_CPL
- URL
- http://dblp.uni-trier.de/db/journals/mst/mst58.html#journals/mst/XiaoN16
- ID情報
-
- DOI : 10.1007/s00224-015-9612-x
- ISSN : 1432-4350
- eISSN : 1433-0490
- DBLP ID : journals/mst/XiaoN16
- J-Global ID : 201702201270738826
- Web of Science ID : WOS:000373747200002