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.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom