(1 + ρ)-Approximation for Selected-Internal Steiner Minimum Tree

DOI10.1007/978-3-540-69733-6_56MaRDI QIDQ3511368zbMATH OpenOpenAlexFDO

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

Publication date 10 July 2008

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-69733-6_56

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Recommendations

• A better constant-factor approximation for selected-internal Steiner minimum tree
• Approximating the selected-internal Steiner tree
• On the Internal Steiner Tree Problem
• MAX-SNP Hardness and Approximation of Selected-Internal Steiner Trees
• 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?)
• Advances in Steiner trees
• Approximating the selected-internal Steiner tree
• On component-size bounded Steiner trees
• 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

(6)

• The Clustered Selected-Internal Steiner Tree Problem
• An improved approximation algorithm for the partial-terminal Steiner tree problem with edge cost 1 or 2
• On the Internal Steiner Tree Problem
• A better constant-factor approximation for selected-internal Steiner minimum tree
• Approximating the selected-internal Steiner tree
• MAX-SNP Hardness and Approximation of Selected-Internal Steiner Trees

This page was built for publication: (1 + ρ)-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 Q3511368)