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

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Aug 01, 1988
Accession Number
ADA199769

Entities

People

  • Bezalel Gavish
  • Jean Choquette
  • Moshe Dror

Organizations

  • Naval Postgraduate School

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • Classification
  • Communication Systems
  • Computer Programming
  • Coverings
  • Integer Programming
  • Iterations
  • Linear Programming
  • Mathematical Programming
  • Naval Warfare
  • Numbers
  • Operations Research
  • Parallel Computing
  • Parallel Processing
  • Real Numbers
  • Schools
  • Security

Readers

  • Calculus or Mathematical Analysis
  • Graph Algorithms and Convex Optimization.