Directed Steiner tree problem on a graph
Subtitle: models, relaxations, and algorithms
By: Moshe Dror, Bezalel Gavish, and Jean Choquette
Contributors: Gavish, Bezalel; Choquette, Jean; Naval Postgraduate School (U.S.). Dept. of Administrative Sciences
Publisher: Naval Postgraduate School; Available from National Technical Information Service
Published: 1988
Place of publication: Monterey, Calif; Springfield, Va
Language: eng
Number of pages: 23
Subjects: GRAPHS; TREES
Other titles: NPS-54-88-010.
Description: 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. (KR)
Notes: Title from cover.

"NPS-54-88-010."

"August 1988."

AD A199 769.

Includes bibliographical references (p. 22-23).

aq/aq cc:9116 10/02/98