Minimizing path lengths in rectilinear Steiner minimum trees with fixed topology

DOI10.1016/J.ORL.2016.10.010zbMATH Open1408.90297OpenAlexW2544484530MaRDI QIDQ1709982FDOQ1709982

Authors: Annika Kristina Kiefner 

Publication date: 15 January 2019

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.orl.2016.10.010

Recommendations

• The rectilinear Steiner tree problem with given topology and length restrictions
• Shortest trees and Steiner trees with rectilinear distances
• scientific article; zbMATH DE number 1086912
• The shortest network under a given topology
• \(1\)-line minimum rectilinear Steiner trees and related problems

zbMATH Keywords

VLSI designSteiner trees with given topologyrectilinear Steiner tree problemsignal delays

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Trees (05C05) Graph theory (including graph drawing) in computer science (68R10)

Cites Work

• The Rectilinear Steiner Tree Problem is $NP$-Complete
• How to find Steiner minimal trees in Euclidean \(d\)-space
• The rectilinear Steiner tree problem with given topology and length restrictions
• Title not available (Why is that?)
• On exact solutions for the rectilinear Steiner tree problem. I: Theoretical results
• Delay-related secondary objectives for rectilinear Steiner minimum trees.
• Steiner trees with bounded RC-delay
• On Steiner Minimal Trees with Rectilinear Distance
• Shallow-light Steiner arborescences with vertex delays
• Balancing minimum spanning trees and shortest-path trees
• Locating the vertices of a steiner tree in an arbitrary metric space
• Rectilinear steiner trees: Efficient special-case algorithms
• Thirty‐five‐point rectilinear steiner minimal trees in a day
• Dijkstra meets Steiner: a fast exact goal-oriented Steiner tree algorithm
• Title not available (Why is that?)

Cited In (6)

• Title not available (Why is that?)
• Shortest paths in linear time on minor-closed graph classes, with an application to Steiner tree approximation
• Title not available (Why is that?)
• Minimum rectilinear Steiner tree of \(n\) points in the unit square
• Path Minima in Incremental Unrooted Trees
• The rectilinear Steiner tree problem with given topology and length restrictions

This page was built for publication: Minimizing path lengths in rectilinear Steiner minimum trees with fixed topology

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