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.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 70-79 |
| Number of pages | 10 |
| Journal | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
| Volume | 3967 LNCS |
| DOIs | |
| State | Published - 2006 |
| Event | 1st International Computer Science Symposium in Russia, CSR 2006 - St. Petersburg, Russian Federation Duration: Jun 8 2006 → Jun 12 2006 |
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- General Computer Science