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.
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Computer Networks and Communications
- Computational Theory and Mathematics
- Applied Mathematics