Generalised \(k\)-Steiner tree problems in normed planes

DOI10.1007/s00453-013-9780-5zbMath1307.68083arXiv1111.1464OpenAlexW2063473778WikidataQ61714604 ScholiaQ61714604MaRDI QIDQ2258073

Marcus Brazil, Doreen Anne Thomas, Konrad J. Swanepoel, Charl J. Ras

Publication date: 2 March 2015

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1111.1464

zbMATH Keywords

polynomial time algorithmnetwork optimisation\(k\)-Steiner treebottleneck Steiner problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items (5)

On the minimum number of Steiner points of constrained 1-line-fixed Steiner tree in the Euclidean plane \(\mathbb{R}^2\) ⋮ The bottleneck 2-connected \(k\)-Steiner network problem for \(k \leq 2\) ⋮ An exact algorithm for the bottleneck 2-connected \(k\)-Steiner network problem in \(L_p\) planes ⋮ On the restricted 1-Steiner tree problem ⋮ On the restricted \(k\)-Steiner tree problem

Cites Work

• Unnamed Item
• Unnamed Item
• Exact algorithms for the bottleneck Steiner tree problem
• On exact solutions to the Euclidean bottleneck Steiner tree problem
• Steiner trees for fixed orientation metrics
• Transitions in geometric minimum spanning trees
• Optimal and approximate bottleneck Steiner trees
• The 1-steiner tree problem
• The shortest network under a given topology
• Degree-five Steiner points cannot reduce network costs for planar sets
• A New Method for the Multifacility Minimax Location Problem
• Combinatorial optimization. Theory and algorithms.

This page was built for publication: Generalised \(k\)-Steiner tree problems in normed planes