## Abstract

We present some fundamental structural properties for minimum length

networks (known as Steiner minimum trees) interconnecting a given set of

points in an environment in which edge segments are restricted to uniformly oriented directions. We show that the edge segments of any full

component of such a tree contain a total of at most 4 directions if is not a

multiple of , or 6 directions if is a multiple of . This result allows us to

develop useful canonical forms for these full components.

The structural properties of these Steiner minimum trees are then used to

resolve an important open problem in the area: does there exist a polynomialtime algorithm for constructing a Steiner minimum tree, if the topology of

the tree is known? We obtain a simple linear time algorithm for constructing a Steiner minimum tree for any given set of points and a given Steiner

topology.

networks (known as Steiner minimum trees) interconnecting a given set of

points in an environment in which edge segments are restricted to uniformly oriented directions. We show that the edge segments of any full

component of such a tree contain a total of at most 4 directions if is not a

multiple of , or 6 directions if is a multiple of . This result allows us to

develop useful canonical forms for these full components.

The structural properties of these Steiner minimum trees are then used to

resolve an important open problem in the area: does there exist a polynomialtime algorithm for constructing a Steiner minimum tree, if the topology of

the tree is known? We obtain a simple linear time algorithm for constructing a Steiner minimum tree for any given set of points and a given Steiner

topology.

Original language | English |
---|---|

Place of Publication | København |

Publisher | Københavns Universitet - Datalogisk Institut |

Number of pages | 26 |

Publication status | Published - 2002 |

### Publication series

Name | DIKU-rapport |
---|---|

No. | 22 |

Volume | 02 |

## Keywords

- steiner tree
- steiner minimum tree
- Algorithms