Directed Steiner tree problem on a graph: Models, relaxations, and algorithms
MetadataShow full item record
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 NumberNPS-54-88-010
Showing items related by title, author, creator and subject.
Merz, Sarah K.; Rasmussen, Craig W.; Lundgren, J. Richard; Maybee, John Stanley (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 ...
Lundgren, J. Richard; Merz, Sarah K.; Maybee, John S.; Rasmussen, Craig W. (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 Colwell, Samuel C., III (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 ...