Indexed by:
Abstract:
Graph routing problem (GRP) and its generalizations have been extensively studied because of their broad applications in the real world. In this paper, we study a variant of GRP called the general cluster routing problem (GCRP). Let G=(V,E) be a complete undirected graph with edge weight c(e) satisfying the triangle inequality. The vertex set is partitioned into a family of clusters C1,.., Cm. We are given a required vertex subset V¯ ⊆ V and a required edge subset E¯ ⊆ E. The aim is to compute a minimum cost tour that visits each vertex in V¯ exactly once and traverses each edge in E¯ at least once, while the vertices and edges of each cluster are visited consecutively. When the starting and ending vertices of each cluster are specified, we devise an approximation algorithm via incorporating Christofides’ algorithm with minimum weight bipartite matching, achieving an approximation ratio that equals the best approximation ratio of path TSP. Then for the case there are no specified starting and ending vertices for each cluster, we propose a more complicated algorithm with a compromised ratio of 2.67 by employing directed spanning tree against the designated auxiliary graph. Both approximation ratios improve the state-of-art approximation ratio that are respectively 2.4 and 3.25. © 2021, Springer Nature Switzerland AG.
Keyword:
Reprint 's Address:
Email:
Source :
ISSN: 0302-9743
Year: 2021
Volume: 12606 LNCS
Page: 264-273
Language: English
0 . 4 0 2
JCR@2005
Cited Count:
SCOPUS Cited Count:
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 2
Affiliated Colleges: