The Rectilinear Steiner Tree Problem with Given Topology and Length Restrictions

DOI10.1007/978-3-319-21398-9_35zbMath1465.68215arXiv1412.5010OpenAlexW3105668836MaRDI QIDQ3196405

Jens Maßberg

Publication date: 29 October 2015

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

dynamic programmingtotal unimodularityrectilinear Steiner treesshallow light Steiner treesSteiner trees with given topology

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items (2)

Embedding rectilinear Steiner trees with length restrictions ⋮ Minimizing path lengths in rectilinear Steiner minimum trees with fixed topology

Cites Work

• Unnamed Item
• Unnamed Item
• The rectilinear Steiner arborescence problem
• Approximating the weight of shallow Steiner trees
• The repeater tree construction problem
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• The Rectilinear Steiner Arborescence Problem Is NP-Complete
• On Steiner’s Problem with Rectilinear Distance

This page was built for publication: The Rectilinear Steiner Tree Problem with Given Topology and Length Restrictions