返回Google圖書搜尋

Applications of the Matroid Parity Problem to Approximating Steiner Trees

Piotr BermanMartin FurerAlexander Z. Zelikovsky

出版	UCLA Computer Science Department, 1998
URL	http://books.google.com.hk/books?id=4s_sGwAACAAJ&hl=&source=gbs_api

註釋Abstract: "The Steiner tree problem in graphs requires to find a minimum size connected subgraph containing a given subset of nodes (given points). In this paper we consider this problem in three classes of graphs: where the maximum path distance is 2, where given points form a dominating set and where the given points form a vertex cover. As all these problems are MAX-SNP hard, the issue is what approximation can be obtained in polynomial time. In the first case we obtain an approximation ratio (of the achieved size over the minimal one) 5/4 + 3/80 = 1.2875, in the second case we achieve 4/3, and in the last case we achieve 8/7 - 1/160."