TY - BOOK

T1 - Algorithms for Plane Steiner Tree Problems

AU - Zachariasen, Martin Tvede

PY - 1998

Y1 - 1998

N2 - Topological network design is the process of planning the layout of a network subject to constraints on topology. Applications include the design of transportation and communication networks where the construction costs typically are associated with the nodes and/or edges of the network. The Steiner tree problem is one of the fundamental topological network design problems. The problem is to interconnect (a subset of) the nodes such that there is a path between every pair of nodes while minimizing the total cost of selected edges. Originally, the Steiner tree problem was stated as a purely geometric problem: Given a set of points (terminals) in the plane, construct a tree interconnecting all terminals such that the total length of all line segments is minimized. In the Euclidean Steiner tree problem, the length of a line segment is the usual Euclidean (or L 2 ) distance between the endpoints of the segment. Correspondingly, in the rectilinear Steiner tree problem distances are measured using the rectilinear (or L1) distance metric.

AB - Topological network design is the process of planning the layout of a network subject to constraints on topology. Applications include the design of transportation and communication networks where the construction costs typically are associated with the nodes and/or edges of the network. The Steiner tree problem is one of the fundamental topological network design problems. The problem is to interconnect (a subset of) the nodes such that there is a path between every pair of nodes while minimizing the total cost of selected edges. Originally, the Steiner tree problem was stated as a purely geometric problem: Given a set of points (terminals) in the plane, construct a tree interconnecting all terminals such that the total length of all line segments is minimized. In the Euclidean Steiner tree problem, the length of a line segment is the usual Euclidean (or L 2 ) distance between the endpoints of the segment. Correspondingly, in the rectilinear Steiner tree problem distances are measured using the rectilinear (or L1) distance metric.

KW - Algorithms

KW - Plane Steiner Tree problems

UR - https://core.ac.uk/download/pdf/269070825.pdf

M3 - Commissioned report

T3 - DIKU-rapport

BT - Algorithms for Plane Steiner Tree Problems

PB - Museum Tusculanum Press

ER -