Canonical forms and algorithms for Steiner trees in uniform orientation metrics

DOI10.1007/s00453-005-1178-6zbMath1095.68074OpenAlexW2080749203WikidataQ61714627 ScholiaQ61714627MaRDI QIDQ2498405

Doreen Anne Thomas, Martin Zachariasen, Marcus Brazil, Jia Feng Weng

Publication date: 16 August 2006

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.11.7843

zbMATH Keywords

linear time algorithm

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (9)

Rotationally optimal spanning and Steiner trees in uniform orientation metrics ⋮ HARDNESS AND APPROXIMATION OF OCTILINEAR STEINER TREES ⋮ THE UNIFORM ORIENTATION STEINER TREE PROBLEM IS NP-HARD ⋮ Minimum Manhattan network problem in normed planes with polygonal balls: a factor 2.5 approximation algorithm ⋮ The GeoSteiner software package for computing Steiner trees in the plane: an updated computational study ⋮ Steiner hull algorithm for the uniform orientation metrics ⋮ Approximating minimum Steiner point trees in Minkowski planes ⋮ Flexibility of Steiner trees in uniform orientation metrics ⋮ Steiner trees for fixed orientation metrics

This page was built for publication: Canonical forms and algorithms for Steiner trees in uniform orientation metrics