Abstract
We present a straighforward proof that the uniform orien-
tation 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.
tation 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.
| Original language | English |
|---|---|
| Title of host publication | Computational complexity for uniform orientation steiner tree problems |
| Place of Publication | Australia |
| Publisher | Australian Computer Society |
| Pages | 107-113 |
| Number of pages | 7 |
| Volume | 135 |
| ISBN (Print) | 978-1-921770-20-3 |
| Publication status | Published - 2013 |
Keywords
- Steiner tree problem
- λ-geometry
- computational complexity
- NP-hard