(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

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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
• The full Steiner tree problem
• Approximating the selected-internal Steiner tree
• Advances in Steiner trees
• On component-size bounded Steiner trees

Cited In (3)

• The Clustered Selected-Internal Steiner Tree Problem
• An improved approximation algorithm for the partial-terminal Steiner tree problem with edge cost 1 or 2
• Approximating the selected-internal Steiner tree

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)