.png){kind=icon}
返回
An approximation algorithm for the k-fixed depots problem
.png){kind=icon}
PRE
AI
DOI：10.1016/j.cie.2017.06.022.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
In this paper, we consider the k-Depots Hamiltonian Path Problem (k-DHPP) of searching k paths in a graph G, starting from k fixed vertices and spanning all the vertices of G. We propose an approximation algorithm for solving the k-DHPP, where the underlying graph is cubic and 2-vertex-connected. Then, we prove the existence of a 5/3-approximation algorithm that gives a solution with total cost at most (5/3n - 4k-2/3). In this case, the proposed method is based upon searching for a perfect matching, constructing an Eulerian graph and finally a k paths solution, following the process of removing/adding edges. We also present an approximation algorithm for finding a shortest tour passing through all vertices in a factor-critical and 2-vertex connected graph. The proposed algorithm achieves a 7/6-approximation ratio where the principle of the method is based on decomposing the graph into a series of ears. (C) 2017 Published by Elsevier Ltd.
Keyword:
Approximation
Cubic
Factor-critical
k-Depots
TSP
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
6.5
论文数:
1.0W
被引数:
3.8W
机构
引用论文
.png){kind=icon}
THE VEHICLE-ROUTING PROBLEM - AN OVERVIEW OF EXACT AND APPROXIMATE ALGORITHMS车辆路径问题-精确算法和近似算法的概述
PREAI
分享收藏
TRANSFORMATION OF MULTIDEPOT MULTISALESMEN PROBLEM TO THE STANDARD TRAVELING SALESMAN PROBLEM多车辆段多业务员问题转化为标准旅行商问题
PREAI
分享收藏
查看更多内容