## 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