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

DOI10.1007/978-3-540-69733-6_56zbMATH Open1148.05318OpenAlexW1552177397MaRDI QIDQ3511368FDOQ3511368

Donghyun Kim, Feng Zou, Yaochun Huang, Xianyue Li, 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

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

Mathematics Subject Classification ID

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

Cites Work

• The Steiner problem in phylogeny is NP-complete
• Thek-Steiner Ratio in Graphs
• The Steiner tree problem
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• The Complexity of Computing Steiner Minimal Trees
• Title not available (Why is that?)
• The full Steiner tree problem
• Approximating the selected-internal Steiner tree
• Title not available (Why is that?)
• Advances in Steiner trees
• On component-size bounded Steiner trees
• Title not available (Why is that?)

Cited In (5)

• 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
• 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)