Abstract
shortest network interconnecting a given set of points under a fixed topology can be computed by solving a linear programming problem whose size is bounded by a polynomial in the number of terminals and the number of legal orientations. When the given topology is restricted to a Steiner topology, our result implies that the Steiner minimum tree under a given Steiner topology can be computed in polynomial time in any given uniform orientation metric with A legal orientations for any fixed integer A > 2. This settles an open problem posed in a recent paper [3].
Original language | English (US) |
---|---|
Pages (from-to) | 1118-1121 |
Number of pages | 4 |
Journal | IEEE Transactions on Computers |
Volume | 51 |
Issue number | 9 |
DOIs | |
State | Published - 2002 |
ASJC Scopus subject areas
- Software
- Theoretical Computer Science
- Hardware and Architecture
- Computational Theory and Mathematics