6533b85afe1ef96bd12b8a22

RESEARCH PRODUCT

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

Joschka KupilasRouven NaujoksErnst Althaus

subject

Discrete mathematicsK-ary treeGeneral Computer ScienceMinimum spanning treek-minimum spanning treeSteiner tree problemTheoretical Computer ScienceCombinatoricssymbols.namesakeHamming graphsymbolsMetric treeGomory–Hu treeMathematicsVantage-point tree

description

While it is known that the d-dimensional Steiner minimum tree problem in Hamming metric is NP-complete if d is part of the input, it is an open question whether this also holds for fixed dimensions. In this paper, this question is answered by showing that the Steiner minimum tree problem in Hamming metric is already NP-complete in 3 dimensions. Furthermore, we show that, the minimum spanning tree gives a 2-2d approximation on the Steiner minimum tree for d>=2. Using this result, we analyse the so-called k-LCA and A"k approximation algorithms and show improved approximation guarantees for low dimensions.

yearjournalcountryeditionlanguage
2013-09-01Theoretical Computer Science
https://doi.org/10.1016/j.tcs.2013.02.011