A better constant-factor approximation for selected-internal Steiner minimum tree

DOI10.1007/S00453-009-9301-8MaRDI QIDQ848949zbMATH OpenOpenAlexFDO

Authors Xianyue Li, Feng Zou, Yaochun Huang, Donghyun Kim, Weili Wu

Publication date 23 February 2010

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-009-9301-8

zbMATH Keywords

approximation algorithmselected-internal Steiner tree

Mathematics Subject Classification ID

Approximation algorithms (68W25)

Recommendations

• (1 + ρ)-Approximation for Selected-Internal Steiner Minimum Tree
• Approximating the selected-internal Steiner tree
• MAX-SNP Hardness and Approximation of Selected-Internal Steiner Trees
• On the Internal Steiner Tree Problem
• The Clustered Selected-Internal Steiner Tree Problem

Cites work

• scientific article; zbMATH DE number 4191148 (Why is no real title available?)
• scientific article; zbMATH DE number 750011 (Why is no real title available?)
• scientific article; zbMATH DE number 1445376 (Why is no real title available?)
• scientific article; zbMATH DE number 2209521 (Why is no real title available?)
• A note on the terminal Steiner tree problem
• Algorithms for terminal Steiner trees
• Approximating the selected-internal Steiner tree
• On approximation algorithms for the terminal Steiner tree problem
• On component-size bounded Steiner trees
• On the terminal Steiner tree problem.
• The Complexity of Computing Steiner Minimal Trees
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• The Steiner problem in phylogeny is NP-complete
• The Steiner tree problem
• The full Steiner tree problem
• Thek-Steiner Ratio in Graphs

Cited in

(7)

• On the clustered Steiner tree problem
• Approximating the selected-internal Steiner tree
• On the clustered Steiner tree problem
• (1 + ρ)-Approximation for Selected-Internal Steiner Minimum Tree
• Algorithms for the minimum diameter terminal Steiner tree problem
• The Clustered Selected-Internal Steiner Tree Problem
• An improved approximation algorithm for the partial-terminal Steiner tree problem with edge cost 1 or 2

This page was built for publication: A better constant-factor approximation for selected-internal Steiner minimum tree

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q848949)