Worst-case ratios of networks in the rectilinear plane

DOI10.1002/net.1031zbMath0990.68101OpenAlexW2162272700MaRDI QIDQ2764995

Ulrich Brenner, Jens Vygen

Publication date: 14 January 2002

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/net.1031

zbMATH Keywords

Steiner treerectilinear network

Mathematics Subject Classification ID

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

Related Items (3)

Two-level rectilinear Steiner trees ⋮ Minimum rectilinear Steiner tree of \(n\) points in the unit square ⋮ Mathematical methods for physical layout of printed circuit boards: an overview

Cites Work

• Unnamed Item
• Unnamed Item
• On Steiner trees for bounded point sets
• Modeling hypergraphs by graphs with the same mincut properties
• Spectral partitioning with multiple eigenvectors
• Time bounds for selection
• Computing mimicking networks
• On minimum stars and maximum matchings.
• On Steiner Minimal Trees with Rectilinear Distance
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• The largest minimal rectilinear steiner trees for a set of n points enclosed in a rectangle with given perimeter
• On Steiner’s Problem with Rectilinear Distance

This page was built for publication: Worst-case ratios of networks in the rectilinear plane