Two-level rectilinear Steiner trees

DOI10.1016/j.comgeo.2016.11.002zbMath1366.05026arXiv1501.00933OpenAlexW2152565327MaRDI QIDQ2362106

Stephan Held, Nicolas Kämmerling

Publication date: 5 July 2017

Published in: Computational Geometry (Search for Journal in Brave)

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

zbMATH Keywords

VLSI designapproximation algorithmsSteiner trees

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Trees (05C05) Approximation algorithms (68W25)

Cites Work

• On the complexity of approximating TSP with neighborhoods and related problems
• The hierarchical network design problem
• On the clustered Steiner tree problem
• Worst-case ratios of networks in the rectilinear plane
• Improved LP-Rounding Approximation Algorithm for k-level Uncapacitated Facility Location
• The Recoverable Robust Two-Level Network Design Problem
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• An O(n logn) heuristic for steiner minimal tree problems on the euclidean metric
• On the Exact Location of Steiner Points in General Dimension
• Reducing the Steiner Problem in a Normed Space
• A Dual-Based Algorithm for Multi-Level Network Design
• A polyhedral study of a two level facility location model
• Max flows in O(nm) time, or better
• On Steiner’s Problem with Rectilinear Distance

This page was built for publication: Two-level rectilinear Steiner trees