An Improved-time Polynomial-space Exact Algorithm for TSP in Degree-5 Graphs

• Item type: Journal(1)
• 公開日: 2017-08-15
• タイトル: An Improved-time Polynomial-space Exact Algorithm for TSP in Degree-5 Graphs
• タイトル / 言語: en
• タイトル: An Improved-time Polynomial-space Exact Algorithm for TSP in Degree-5 Graphs
• 言語: eng
• キーワード / 主題Scheme: Other
• キーワード / 主題: [特集：離散と計算の幾何・グラフ・ゲーム] Traveling Salesman Problem, exact exponential algorithm, branch-and-reduce, measure-and-conquer
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: Technical University of Malaysia Malacca
• 著者所属: Department of Applied Mathematics and Physics, Graduate School of Informatics, Kyoto University
• 著者所属: Department of Applied Mathematics and Physics, Graduate School of Informatics, Kyoto University
• 著者所属(英): en
• 著者所属(英): Technical University of Malaysia Malacca
• 著者所属(英): en
• 著者所属(英): Department of Applied Mathematics and Physics, Graduate School of Informatics, Kyoto University
• 著者所属(英): en
• 著者所属(英): Department of Applied Mathematics and Physics, Graduate School of Informatics, Kyoto University
• 著者名: Norhazwani, Md Yunos; Aleksandar, Shurbevski; Hiroshi, Nagamochi
• 著者名(英): Norhazwani, Md Yunos; Aleksandar, Shurbevski; Hiroshi, Nagamochi
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: The Traveling Salesman Problem (TSP) is one of the most well-known NP-hard optimization problems. Following a recent trend of research which focuses on developing algorithms for special types of TSP instances, namely graphs of limited degree, in an attempt to reduce a part of the time and space complexity, we present a polynomial-space branching algorithm for the TSP in an n-vertex graph with degree at most 5, and show that it has a running time of O*(2.3500n), which improves the previous best known time bound of O*(2.4723n) given by the authors (the 12th International Symposium on Operations Research and Its Application (ISORA 2015), pp.45-58, 2015). While the base of the exponent in the running time bound of our algorithm is greater than 2, it still outperforms Gurevich and Shelah's O*(4n nlog n) polynomial-space exact algorithm for the TSP in general graphs (SIAM Journal of Computation, Vol.16, No.3, pp.486-502, 1987). In the analysis of the running time, we use the measure-and-conquer method, and we develop a set of branching rules which foster the analysis of the running time.; ------------------------------; This is a preprint of an article intended for publication Journal of; Information Processing(JIP). This preprint should not be cited. This; article should be cited as: Journal of Information Processing Vol.25(2017) (online); DOI http://dx.doi.org/10.2197/ipsjjip.25.639; ------------------------------
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: The Traveling Salesman Problem (TSP) is one of the most well-known NP-hard optimization problems. Following a recent trend of research which focuses on developing algorithms for special types of TSP instances, namely graphs of limited degree, in an attempt to reduce a part of the time and space complexity, we present a polynomial-space branching algorithm for the TSP in an n-vertex graph with degree at most 5, and show that it has a running time of O*(2.3500n), which improves the previous best known time bound of O*(2.4723n) given by the authors (the 12th International Symposium on Operations Research and Its Application (ISORA 2015), pp.45-58, 2015). While the base of the exponent in the running time bound of our algorithm is greater than 2, it still outperforms Gurevich and Shelah's O*(4n nlog n) polynomial-space exact algorithm for the TSP in general graphs (SIAM Journal of Computation, Vol.16, No.3, pp.486-502, 1987). In the analysis of the running time, we use the measure-and-conquer method, and we develop a set of branching rules which foster the analysis of the running time.; ------------------------------; This is a preprint of an article intended for publication Journal of; Information Processing(JIP). This preprint should not be cited. This; article should be cited as: Journal of Information Processing Vol.25(2017) (online); DOI http://dx.doi.org/10.2197/ipsjjip.25.639; ------------------------------
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00116647
• 書誌情報: 情報処理学会論文誌; 巻 58, 号 8, 発行日 2017-08-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7764