| Conţinutul numărului revistei |
| Articolul precedent |
| Articolul urmator |
 153 0 |
 SM ISO690:2012ZELIKOVSKY, Alexander. An 11/6-approximation algorithm for the network steiner problem. In: Algorithmica, 1993, vol. 9, pp. 463-470. ISSN 0178-4617. DOI: https://doi.org/10.1007/BF01187035 |
| EXPORT metadate: Google Scholar Crossref CERIF DataCite Dublin Core |
  Algorithmica |
||||||
| Volumul 9 / 1993 / ISSN 0178-4617 /ISSNe 1432-0541 | ||||||
|
||||||
| DOI:https://doi.org/10.1007/BF01187035 | ||||||
| Pag. 463-470 | ||||||
|
||||||
| Rezumat | ||||||
An instance of the Network Steiner Problem consists of an undirected graph with edge lengths and a subset of vertices; the goal is to find a minimum cost Steiner tree of the given subset (i.e., minimum cost subset of edges which spans it). An 11/6-approximation algorithm for this problem is given. The approximate Steiner tree can be computed in the time 0(|V| |E| + |S|4), where V is the vertex set, E is the edge set of the graph, and S is the given subset of vertices. |
||||||
| Cuvinte-cheie Approximation algorithm, Steiner tree |
||||||
|
|
|
|
