Computational Complexity for Uniform Orientation Steiner Tree Problems

Brazil, M. and Zachariasen, M.

We present a straighforward proof that the uniform orientation Steiner tree problem, also known as the �-geometry Steiner tree problem, is NP-hard whenever the number of orientations, �, is a multiple of 3. We also briefly outline how this result can be generalised to every � > 2.

Cite as: Brazil, M. and Zachariasen, M. (2013). Computational Complexity for Uniform Orientation Steiner Tree Problems. In Proc. Computer Science 2013 (ACSC 2013) Adelaide, Australia. CRPIT, 135. Thomas, B. Eds., ACS. 107 - 114

(from crpit.com) (local if available)