| Applications of the Linear Matroid Parity Algorithm to Approximating Steiner Trees (2008) | |||||||||||||||||
Abstract | |||||||||||||||||
| The Steiner tree problem in unweighted graphs requires to find a minimum size connected subgraph containing a given subset of nodes (terminals). In this paper we investigate applications of the linear matroid parity algorithm to the Steiner tree problem for two classes of graphs: where the terminals form a vertex cover and where terminals form a dominating set. As all these problems are MAX-SNP-hard, the issue is what approximation can be obtained in polynomial time. The previously best approximation ratio for the first class of graphs (also known as unweighted quasi-bipartite graphs) is ≈ 1.217 (Gröpl et al. [4]) is reduced in this paper to 8/7 − 1/160 ≈ 1.137. For the case of graphs where terminals form a dominating set, an approximation ratio of 4/3 is achieved. | |||||||||||||||||
Publication details | |||||||||||||||||
| |||||||||||||||||