Abstract
In a recent paper [2], a linear programming formulation was given for
the problem of computing a shortest network under a fixed topology (under the
-metric). We point out a nontrivial error in this paper and give a correct and
simpler linear programming formulation. We also show that the result can be
generalized to any distance function given by a Minkowski unit circle that is a
centrally symmetric polygon.
the problem of computing a shortest network under a fixed topology (under the
-metric). We point out a nontrivial error in this paper and give a correct and
simpler linear programming formulation. We also show that the result can be
generalized to any distance function given by a Minkowski unit circle that is a
centrally symmetric polygon.
| Original language | English |
|---|---|
| Pages (from-to) | 783-784 |
| Number of pages | 2 |
| Journal | IEEE Transactions on Computers |
| Volume | 55 |
| Issue number | 6 |
| DOIs |
|
| Publication status | Published - 2006 |
Keywords
- Steiner trees
- shortest network under a fixed topology
- polygonal minkowski unit circle
- linear programming