# Approximation algorithms for the p-hub center routing problem in parameterized metric graphs

Li Hsuan Chen, Sun Yuan Hsieh, Ling Ju Hung, Ralf Klasing

1 引文 斯高帕斯（Scopus）

## 摘要

A complete weighted graph G = (V, E,w) is called Δβ-metric, for some β ≥ 1/2, if G satisfies the β-triangle inequality, i.e., w(u, v) ≤ β · (w(u, x) + w(x, v)) for all vertices u, v, x ∈ V. Given a Δβ -metric graph G = (V, E,w), the Single Allocation at most p-Hub Center Routing problem is to find a spanning subgraph H* of G such that (i) any pair of vertices in C* is adjacent in H* where C* ⊂ V and |C*|≤p; (ii) any pair of vertices in V\C* is not adjacent in H*; (iii) each v∈V\C* is adjacent to exactly one vertex in C*; and (iv) the routing cost (Formula Presented) is minimized where (Formula Presented) and f*(u),f* (v) are the vertices in C* adjacent to u and v in H*, respectively. Note that (Formula Presented) if v∈C*. The vertices selected in C* are called hubs and the rest of vertices are called non-hubs. In this paper, we show that the Single Allocation at most p-Hub Center Routing problem is NP-hard in Δβ-metric graphs for any β>1/2. Moreover, we give 2β-approximation algorithms running in time O(n2) for any β>1/2 where n is the number of vertices in the input graph.

原文 English Combinatorial Algorithms - 29th International Workshop, IWOCA 2018, Proceedings Hon Wai Leong, Costas Iliopoulos, Wing-Kin Sung Springer Verlag 115-127 13 9783319946665 https://doi.org/10.1007/978-3-319-94667-2_10 Published - 2018 29th International Workshop on Combinatorial Algorithms, IWOCA 2018 - Singapore, Singapore持續時間: 2018 七月 16 → 2018 七月 19

### 出版系列

名字 Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 10979 LNCS 0302-9743 1611-3349

### Other

Other 29th International Workshop on Combinatorial Algorithms, IWOCA 2018 Singapore Singapore 18-07-16 → 18-07-19

## All Science Journal Classification (ASJC) codes

• Theoretical Computer Science
• Computer Science(all)