The rectilinear Steiner tree problem with given topology and length restrictions

DOI10.1007/978-3-319-21398-9_35zbMATH Open1465.68215arXiv1412.5010OpenAlexW3105668836MaRDI QIDQ3196405FDOQ3196405

Authors: Jens Maßberg 

Publication date: 29 October 2015

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

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.

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

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

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)

Cites Work

• Approximating the weight of shallow Steiner trees
• Title not available (Why is that?)
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• The rectilinear Steiner arborescence problem
• The repeater tree construction problem
• Title not available (Why is that?)
• The Rectilinear Steiner Arborescence Problem Is NP-Complete
• On Steiner’s Problem with Rectilinear Distance

Cited In (9)

• Logic Programming
• On the restricted 1-Steiner tree problem
• Title not available (Why is that?)
• Title not available (Why is that?)
• Reductions for the rectilinear steiner tree problem
• 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
• Approximation of rectilinear Steiner trees with length restrictions on obstacles.

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)