Premium
On finding steiner vertices
Author(s) -
RaywardSmith V. J.,
Clare A.
Publication year - 1986
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230160305
Subject(s) - steiner tree problem , combinatorics , mathematics , vertex connectivity , graph , spanning tree , minimum degree spanning tree , minimum spanning tree , discrete mathematics , vertex (graph theory)
Given a graph G = ( V, E ), finding the Steiner tree in G for some set of special vertices V ′ ⊂ V ″, is equivalent to finding the minimum spanning tree in the subgraph of G induced by V ′ ∪ V ″, where V ″ is the set of Steiner vertices. In this paper, we consider ways of deciding which vertices of V are in V ″ and compare the performance of various heuristic algorithms.