Approximating Steiner trees in graphs with restricted weights

Approximating Steiner trees in graphs with restricted weights

0.00 Avg rating0 Votes
Article ID: iaor20022447
Country: United States
Volume: 31
Issue: 4
Start Page Number: 283
End Page Number: 292
Publication Date: Jul 1998
Journal: Networks
Authors: , , ,
Keywords: Steiner problem
Abstract:

We analyze the approximation ratio for the average distance heuristic for the Steiner tree problem on graphs and prove nearly tight bounds for the cases of complete graphs with binary weights {1,d} or weights in the interval [1, d], where d ≤ 2. The improvement over other analyzed algorithms is a factor of about e = 2.718.

Reviews

Required fields are marked *. Your email address will not be published.