Affordable Access

Publisher Website

Steiner problem in Halin networks

Authors
Journal
Discrete Applied Mathematics
0166-218X
Publisher
Elsevier
Publication Date
Volume
17
Issue
3
Identifiers
DOI: 10.1016/0166-218x(87)90031-x
Disciplines
  • Computer Science
  • Design

Abstract

Abstract The Steiner problem in networks is concerned with the determination of a minimum cost subnetwork connecting some (not necessarily all) vertices of an underlying network. The decision version of the Steiner problem is known to be NP-complete. However, if the underlying network is outerplanar or series-parallel, linear time algorithms have been developed. In this paper a linear time algorithm for the Steiner problem in Halin networks is presented. This result provides another example where the recursive structure of the underlying network leads to an efficient algorithm. Furthermore, the result is of interest from the network design point of view, since Halin networks are nontrivial generalizations of tree and ring networks.

There are no comments yet on this publication. Be the first to share your thoughts.