• Complex
  • Title
  • Keyword
  • Abstract
  • Scholars
  • Journal
  • ISSN
  • Conference
成果搜索

author:

Guo, Longkun (Guo, Longkun.) [1] (Scholars:郭龙坤) | Xing, Bin (Xing, Bin.) [2] | Huang, Peihuang (Huang, Peihuang.) [3] | Zhang, Xiaoyan (Zhang, Xiaoyan.) [4]

Indexed by:

EI

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:

Approximation algorithms Clustering algorithms Graph algorithms Graph structures Routing algorithms Trees (mathematics)

Community:

  • [ 1 ] [Guo, Longkun]College of Mathematics and Computer Science, Fuzhou University, Fuzhou; 350116, China
  • [ 2 ] [Guo, Longkun]School of Computer Science, Qilu University of Technology (Shandong Academy of Sciences), Jinan; 250353, China
  • [ 3 ] [Xing, Bin]College of Mathematics and Computer Science, Fuzhou University, Fuzhou; 350116, China
  • [ 4 ] [Huang, Peihuang]College of Data Science and Mathematics, Minjiang University, Fuzhou; 350108, China
  • [ 5 ] [Zhang, Xiaoyan]School of Mathematical Science, Nanjing Normal University, Nanjing; 210046, China

Reprint 's Address:

Email:

Show more details

Related Keywords:

Related Article:

Source :

ISSN: 0302-9743

Year: 2021

Volume: 12606 LNCS

Page: 264-273

Language: English

0 . 4 0 2

JCR@2005

Cited Count:

WoS CC 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

Online/Total:117/10040079
Address:FZU Library(No.2 Xuyuan Road, Fuzhou, Fujian, PRC Post Code:350116) Contact Us:0591-22865326
Copyright:FZU Library Technical Support:Beijing Aegean Software Co., Ltd. 闽ICP备05005463号-1