On the low-dimensional Steiner minimum tree problem in Hamming metric

DOI10.1016/j.tcs.2013.02.011zbMath1416.68128OpenAlexW2175906774MaRDI QIDQ393125

Joschka Kupilas, Rouven Naujoks, Ernst Althaus

Publication date: 16 January 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2013.02.011

zbMATH Keywords

approximation algorithmSteiner minimum treeHamming metricSteiner ratio

Mathematics Subject Classification ID

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

Related Items (1)

Insight into the computation of Steiner minimal trees in Euclidean space of general dimension

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The Steiner problem with edge lengths 1 and 2
• The Steiner problem in phylogeny is NP-complete
• On the approximability of the Steiner tree problem in phylogeny
• The Steiner ratio of several discrete metric spaces
• Aligning sequences via an evolutionary tree
• An improved LP-based approximation for steiner tree
• Computing steiner minimum trees in Hamming metric
• Thek-Steiner Ratio in Graphs

This page was built for publication: On the low-dimensional Steiner minimum tree problem in Hamming metric