Title

Probable Performance of Steiner Tree Algorithms

Authors

Bernard M. Waxman, Washington University in St. Louis

Document Type

Technical Report

Publication Date

1988-01-01

Filename

WUCS-88-04.pdf

DOI:

10.7936/K7B856GR

Technical Report Number

WUCS-88-04

Abstract

In this paper we consider the probable performance of three polynomial time approximation algorithms for the Steiner tree problem with respect to a specific random graph model. The Steiner problem asks us to find a minimum cost spanning subgraph (tree) for a subset D of modes in a graph.

Comments

Permanent URL: http://dx.doi.org/10.7936/K7B856GR

Recommended Citation

Waxman, Bernard M., "Probable Performance of Steiner Tree Algorithms" Report Number: WUCS-88-04 (1988). All Computer Science and Engineering Research.
https://openscholarship.wustl.edu/cse_research/761