|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'504'928
Articles rated: 2609
26 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
An improved approximation algorithm for the internal Steiner minimum tree | | Bang Ye Wu
; | | Date: |
15 Jul 2013 | | Abstract: | For a metric graph $G=(V,E)$ and $Rsubset V$, the internal Steiner minimum
tree problem asks for a minimum weight Steiner tree spanning $R$ such that
every vertex in $R$ is not a leaf. This note shows a simple polynomial-time
$2
ho$-approximation algorithm, in which $
ho$ is the approximation ratio for
the Steiner minimum tree problem. The result improves the previous best
approximation ratio $2
ho+1$ for the problem. | | Source: | arXiv, 1307.3822 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER