## Abstract

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) and a center c∈V, and an integer p, the Δ
_{β}
-STAR p-HUB CENTER PROBLEM (Δ
_{β}
-SpHCP) is to find a depth-2 spanning tree T of G rooted at c such that c has exactly p children (also called hubs) and the diameter of T is minimized. In this paper, we study Δ
_{β}
-SpHCP for all [Formula presented]. We show that for any ϵ>0, to approximate the Δ
_{β}
-SpHCP to a ratio g(β)−ϵ is NP-hard and give r(β)-approximation algorithms for the same problem where g(β) and r(β) are functions of β. A subclass of metric graphs is identified that Δ
_{β}
-SpHCP is polynomial-time solvable. Moreover, some r(β)-approximation algorithms given in this paper meet approximation lower bounds.

Original language | English |
---|---|

Pages (from-to) | 92-112 |

Number of pages | 21 |

Journal | Journal of Computer and System Sciences |

Volume | 92 |

DOIs | |

Publication status | Published - 2018 Mar 1 |

## All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Computer Networks and Communications
- Computational Theory and Mathematics
- Applied Mathematics