Abstract: As one kind of NP-hard optimization problem, the Steiner tree problem intents to find a minimum cost tree that satisfies some special requirement in an edge or vertex-weighted graph. Two approximation algorithms, based on the facility location problems,wi

Key words: Steiner tree-star, Facility location, Approximation algorithm, Problem transformation