Directed Steiner tree problem on a graph: Models, relaxations, and algorithms
| dc.contributor.author | Dror, Moshe | |
| dc.contributor.author | Gavish, Bezalel | |
| dc.contributor.author | Choquette, Jean | |
| dc.date | 1988-08 | |
| dc.date.accessioned | 2013-03-07T21:52:32Z | |
| dc.date.available | 2013-03-07T21:52:32Z | |
| dc.date.issued | 1988-08 | |
| dc.identifier.uri | http://hdl.handle.net/10945/29819 | |
| dc.description.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) | en_US |
| dc.description.sponsorship | Prepared for: Naval Postgraduate School Monterey, CA | en_US |
| dc.description.uri | http://archive.org/details/directedsteinert00dror | |
| dc.language.iso | en_US | |
| dc.publisher | Monterey, California. Naval Postgraduate School | en_US |
| dc.subject.lcsh | GRAPHS. | en_US |
| dc.title | Directed Steiner tree problem on a graph: Models, relaxations, and algorithms | en_US |
| dc.type | Technical Report | en_US |
| dc.contributor.corporate | Naval Postgraduate School (U.S.) | |
| dc.contributor.department | NA | |
| dc.subject.author | Lagrangian relaxation, minimum spanning arborescence problem, networks, Steiner Tree Problem | en_US |
| dc.description.funder | O&MN, Direct Funding | en_US |
| dc.description.recognition | NA | en_US |
| dc.identifier.oclc | NA | |
| dc.identifier.npsreport | NPS-54-88-010 | |
| dc.description.distributionstatement | Approved for public release; distribution is unlimited. |
Files in this item
This item appears in the following Collection(s)
-
All Technical Reports Collection
Includes reports from all departments. -
Other Technical Reports
Technical Reports not otherwise gathered in a named collection
Related 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 ...
