Accession Number:

ADA199769

Title:

Directed Steiner Tree Problem on a Graph: Models, Relaxations, and Algorithms

Descriptive Note:

Final rept.

Corporate Author:

NAVAL POSTGRADUATE SCHOOL MONTEREY CA

Report Date:

1988-08-01

Pagination or Media Count:

28.0

Abstract:

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.

Subject Categories:

  • Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE