Multi-Level Steiner Trees.

DOI10.4230/LIPIcs.SEA.2018.15zbMath1493.68397arXiv1804.02627OpenAlexW2963220759MaRDI QIDQ5140725

Martin Gronemann, David Glickenstein, Joseph C. Watkins, Alexander Wolff, Stephen G. Kobourov, Niklas Heinsohn, Faryad Darabi Sahneh, Richard Spence, Reyan Ahmed, Patrizio Angelini, Alon Efrat

Publication date: 16 December 2020

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

zbMATH Keywords

approximation algorithmSteiner treemulti-level graph representation

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (3)

Unnamed Item ⋮ Multi-priority graph sparsification ⋮ Mixed integer programming formulations for Steiner tree and quality of service multicast tree problems

Cites Work

• Unnamed Item
• Unnamed Item
• The Steiner tree problem on graphs: inapproximability results
• The Steiner problem with edge lengths 1 and 2
• Improved approximation algorithms for the quality of service multicast tree problem
• Emergence of Scaling in Random Networks
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• Steiner problem in networks: A survey
• Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
• Modeling and Heuristic Worst-Case Performance Analysis of the Two-Level Network Design Problem
• The Structure and Function of Complex Networks
• Random Geometric Graphs
• On the approximability of some network design problems
• Reducibility among Combinatorial Problems
• Tighter Bounds for Graph Steiner Tree Approximation
• Collective dynamics of ‘small-world’ networks
• Steiner Tree Approximation via Iterative Randomized Rounding
• Steiner Minimal Trees
• The Multi-Tier Tree Problem
• A comparison of Steiner tree relaxations
• Grade of service Steiner minimum trees in the Euclidean plane

This page was built for publication: Multi-Level Steiner Trees.