Fróðskaparrit - 01.01.1999, Page 257

261
News and Progress 1998
Nýtt innan vísindi í 1998
Doctorates Awarded, 1998 / Ársins doktarar, 1998
Martin Zachariasen
Martin Zachariasen, Algorithms for Plane Steiner Tree Problems, Ph.D. thesis,
University of Copenhagen, 1998 (Published as technical report 98/15, Dept. of
Computer Science, University of Copenhagen)
Summary
Topological network design is the process
of planning the layout of a network subject
to the constraints of topology. Applica-
tions, for example, include the design of
transportation and communication net-
works in which the construction costs typi-
cally are associated with the nodes and/or
edges of the network. The Steiner tree
problem is one of the fundamental, topo-
logical 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 minimising the
total cost of selected edges.
Originally, the Steiner tree problem was
stated as a purely geometric problem: Giv-
en a set of points (terminals) in a plane,
construct a tree interconnecting all termi-
nals such that the total length of all line
segments is minimised. In the Euclidean
Steiner tree problem, the length of a line
segment is the usual Euclidean (or L2) dis-
tance between the endpoints of the seg-
ment. Correspondingly, in the rectilinear
Steiner tree problem distances are mea-
Samandráttur
Topologisk netplanlegging snýr seg um at
fastleggja strukturin av einum neti undir
givnum topologiskum treytum. Hetta verð-
ur nýtt í sambandi við gerð av netum til
flutning og samskifti, har kostnaðurin ofta
er tengdur at knútunum ella kantunum í
netinum.
Eitt av teimum grundleggjandi problem-
unum innan topologiska netplanlegging
verður nevnt Steiner problemið. Hetta snýr
seg um at binda saman eina partmongd av
knútunum, soleiðis at øll knútapør hava ein
veg ímillum hvørt annað; samstundis skal
samlaði kostnaðurin minimerast. Uppruna-
liga var Steiner problemið givið sum eitt
reint geometriskt problem: Ein mongd av
punktum (nevnd terminalar) í planinum
skal samanbindast við einum træi, soleiðis
at samlaða longin av øllum linjustykkjun-
um í trænum verður minimerað. I tí euklid-
iska Steinertrænum verður vanliga euklid-
iska (ella L2) fráløgan nýtt til at máta
longdina av linjustykkjunum, meðan tað
rektlinjaða Steinertræið nýtir sonevndu
rektlinjaðu (ella Lj) fráløguna.
Fróðskaparrit 47. bók 1999: 261-136