Directed Steiner tree problem on a graph: Models, relaxations, and algorithms
directedsteinert00dror.pdf (1.500Mb)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. (KR)
NPS Report Number
NPS-54-88-010Related items
Showing items related by title, author, creator and subject.
-
A characterization of graphs with interval two-step graphs
(Monterey, California. Naval Postgraduate School, 1993); NPS-MA-93-021One of the intriguing open problems on competition graphs is determining what digraphs have interval competition graphs. In this paper we consider this problem for the class of loopless symmetric digraphs. Here we first ... -
A Characterization of Graphs With Interval Two-Step Graphs
(Norrth-Holland, 1995);One of the intriguing open problems on competition graphs is determining what digraphs have interval competition graphs. This problem originated in the work of Cohen on food webs. We consider it for the class of loopless ... -
On partitioning an arbitrarily given set of elements of a finite Boolean algebra into the minimum number of sets of compatible elements
(Monterey, California. Naval Postgraduate School, 1964);During the past several years at the United States Naval Postgraduate School there has been much interest in obtaining an efficient method for making a time schedule for classes. A mathematical model for a simplified ...
