Optimal interconnection trees in the plane. Theory, algorithms and applications

DOI10.1007/978-3-319-13915-9zbMath1319.05044OpenAlexW4239626474MaRDI QIDQ2339762

Martin Zachariasen, Marcus Brazil

Publication date: 7 April 2015

Published in: Algorithms and Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-13915-9

zbMATH Keywords

Steiner treeexact algorithmschip designgeometric planesoptimal interconnection networks

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Combinatorics in computer science (68R05) Combinatorial optimization (90C27) Planar graphs; geometric and topological aspects of graph theory (05C10) Hardware implementations of nonnumerical algorithms (VLSI algorithms, etc.) (68W35) Coloring of graphs and hypergraphs (05C15) Distance in graphs (05C12) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

On the minimum number of Steiner points of constrained 1-line-fixed Steiner tree in the Euclidean plane \(\mathbb{R}^2\) ⋮ New pruning rules for the Steiner tree problem and 2-connected Steiner network problem ⋮ Approximate Euclidean Steiner trees ⋮ Minimum Steiner trees on a set of concyclic points and their center ⋮ Solving the prize‐collecting Euclidean Steiner tree problem ⋮ Solving Steiner trees: Recent advances, challenges, and perspectives ⋮ Simplifying obstacles for Steiner network problems in the plane ⋮ Structural properties of minimum multi-source multi-sink Steiner networks in the Euclidean plane ⋮ Network augmentation for disaster‐resilience against geographically correlated failure ⋮ Computational complexity of the 2-connected Steiner network problem in the \(\ell_p\) plane ⋮ Computing minimum 2‐edge‐connected Steiner networks in the Euclidean plane ⋮ Shortest directed networks in the plane ⋮ The GeoSteiner software package for computing Steiner trees in the plane: an updated computational study ⋮ Steiner trees with bounded RC-delay ⋮ On the restricted 1-Steiner tree problem ⋮ Computing skeletons for rectilinearly convex obstacles in the rectilinear plane ⋮ Approximation algorithms for constructing required subgraphs using stock pieces of fixed length ⋮ On the restricted \(k\)-Steiner tree problem ⋮ Approximation algorithms for solving the line-capacitated minimum Steiner tree problem