Directed Steiner Tree Problem on a Graph: Models, Relaxations, and Algorithms
NAVAL POSTGRADUATE SCHOOL MONTEREY CA
Pagination or Media Count:
A Steiner Problem in graphs is the problem of finding a set of edges arcs with minimum total weight which connects a given set of nodes in an edge- weighted graph directed or undirected. This paper develops models for the directed Steiner tree problem on graphs. New and old models are examined in terms of their amenability to solution schemes basd on Lagrangian relaxation. As a result, three algorithms are presented and their performance compared on a number of problems originally tested by Beasley 1984, 1987 in the case of undirected graphs. Keywords Networks, Operations research.
- Operations Research