Applications of the linear matroid parity algorithm to approximating Steiner trees

Piotr Berman, Martin Fürer, Alexander Zelikovsky

Research output: Contribution to journalConference articlepeer-review

5 Scopus citations


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 languageEnglish (US)
Pages (from-to)70-79
Number of pages10
JournalLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume3967 LNCS
StatePublished - 2006
Event1st International Computer Science Symposium in Russia, CSR 2006 - St. Petersburg, Russian Federation
Duration: Jun 8 2006Jun 12 2006

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Applications of the linear matroid parity algorithm to approximating Steiner trees'. Together they form a unique fingerprint.

Cite this