The Steiner tree problem in graphs: Worst case examples for insertion heuristics

The Steiner tree problem in graphs: Worst case examples for insertion heuristics

0.00 Avg rating0 Votes
Article ID: iaor20002345
Country: United Kingdom
Volume: 1
Issue: 1
Start Page Number: 21
End Page Number: 34
Publication Date: Jan 1999
Journal: International Journal of Mathematical Algorithms
Authors:
Keywords: heuristics
Abstract:

Given a graph G with positive edge costs and a subset R of required vertices, the Steiner problem is the determination of a tree in G of minimum total cost spanning R. Several heuristics have been developed for this NP-hard problem. It is well known that any minimum spanning tree T and R for the distance graph of G provides a 2-approximate solution. The tree can often be improved by inserting at most s other vertices into R at a time and repeating while an improvement is possible. Introducing a class of such heuristics INSERT(s), where s=1 corresponds to Minoux's heuristic, we present difficult examples for them and raise a strong conjecture that such heuristics gaurantee to come arbitarily close to the optimum cost in a polynomial time.

Reviews

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