On finding steiner vertices

Abstract

Abstract 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.