The rectilinear Steiner tree problem with given topology and length restrictions

DOI10.1007/978-3-319-21398-9_35MaRDI QIDQ3196405zbMATH OpenOpenAlexFDO

Authors 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

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

Abstract: We consider the problem of embedding the Steiner points of a Steiner tree with given topology into the rectilinear plane. Thereby, the length of the path between a distinguished terminal and each other terminal must not exceed given length restrictions. We want to minimize the total length of the tree. The problem can be formulated as a linear program and therefore it is solvable in polynomial time. In this paper we analyze the structure of feasible embeddings and give a combinatorial polynomial time algorithm for the problem. Our algorithm combines a dynamic programming approach and binary search and relies on the total unimodularity of a matrix appearing in a sub-problem.

Recommendations

• Embedding rectilinear Steiner trees with length restrictions
• Minimizing path lengths in rectilinear Steiner minimum trees with fixed topology
• The Steiner tree problem for terminals on the boundary of a rectilinear polygon
• scientific article; zbMATH DE number 1286271
• Shortest trees and Steiner trees with rectilinear distances

Cites work

• scientific article; zbMATH DE number 1424545 (Why is no real title available?)
• scientific article; zbMATH DE number 3422402 (Why is no real title available?)
• Approximating the weight of shallow Steiner trees
• On Steiner’s Problem with Rectilinear Distance
• The Rectilinear Steiner Arborescence Problem Is NP-Complete
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• The rectilinear Steiner arborescence problem
• The repeater tree construction problem

Cited in

(9)

• Embedding rectilinear Steiner trees with length restrictions
• Reductions for the rectilinear steiner tree problem
• Logic Programming
• The Steiner tree problem for terminals on the boundary of a rectilinear polygon
• scientific article; zbMATH DE number 1445377 (Why is no real title available?)
• Approximation of rectilinear Steiner trees with length restrictions on obstacles.
• Minimizing path lengths in rectilinear Steiner minimum trees with fixed topology
• scientific article; zbMATH DE number 5629773 (Why is no real title available?)
• On the restricted 1-Steiner tree problem

This page was built for publication: The rectilinear Steiner tree problem with given topology and length restrictions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3196405)