MAX-SNP Hardness and Approximation of Selected-Internal Steiner Trees

DOI10.1007/11809678_47zbMATH Open1162.68452OpenAlexW1481078828MaRDI QIDQ3591304FDOQ3591304

Shih-Cheng Yang, Sun-Yuan Hsieh

Publication date: 10 September 2007

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

Full work available at URL: https://doi.org/10.1007/11809678_47

Recommendations

• On the Internal Steiner Tree Problem
• The internal Steiner tree problem: Hardness and approximations
• Approximating the selected-internal Steiner tree
• The bottleneck selected‐internal and partial terminal Steiner tree problems
• (1 + ρ)-Approximation for Selected-Internal Steiner Minimum Tree

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Cited In (4)

• (1 + ρ)-Approximation for Selected-Internal Steiner Minimum Tree
• The Clustered Selected-Internal Steiner Tree Problem
• On the Internal Steiner Tree Problem
• The internal Steiner tree problem: Hardness and approximations

This page was built for publication: MAX-SNP Hardness and Approximation of Selected-Internal Steiner Trees

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