Since 2014
On the Steiner Tree 3/2-Approximation for Quasi-Bipartite Graphs
BRICS Report Series
View Archive Info| Field | Value | |
| Title |
On the Steiner Tree 3/2-Approximation for Quasi-Bipartite Graphs
|
|
| Creator |
Rizzi, Romeo
|
|
| Description |
Let G = (V,E) be an undirected simple graph and w : E -> R+ bea non-negative weighting of the edges of G. Assume V is partitionedas R union X. A Steiner tree is any tree T of G such that every nodein R is incident with at least one edge of T. The metric Steiner treeproblem asks for a Steiner tree of minimum weight, given that w is ametric. When X is a stable set of G, then (G,R,X) is called quasi-bipartite. In [1], Rajagopalan and Vazirani introduced the notion ofquasi-bipartiteness and gave a ( 3/2 + epsilon) approximation algorithm for the metric Steiner tree problem, when (G,R,X) is quasi-bipartite. In thispaper, we simplify and strengthen the result of Rajagopalan and Vazirani.We also show how classical bit scaling techniques can be adaptedto the design of approximation algorithms.Key words: Steiner tree, local search, approximation algorithm, bit scaling.
|
|
| Publisher |
Aarhus University
|
|
| Contributor |
—
|
|
| Date |
1999-12-09
|
|
| Type |
info:eu-repo/semantics/article
info:eu-repo/semantics/publishedVersion — |
|
| Format |
application/pdf
|
|
| Identifier |
https://tidsskrift.dk/brics/article/view/20108
10.7146/brics.v6i39.20108 |
|
| Source |
BRICS Report Series; No 39 (1999): RS-39 On the Steiner Tree 3/2-Approximation for Quasi-Bipartite Graphs
BRICS Report Series; No 39 (1999): RS-39 On the Steiner Tree 3/2-Approximation for Quasi-Bipartite Graphs 1601-5355 0909-0878 |
|
| Language |
eng
|
|
| Relation |
https://tidsskrift.dk/brics/article/view/20108/17727
|
|
| Rights |
Copyright (c) 2015 BRICS Report Series
|
|