HARDNESS AND APPROXIMATION OF OCTILINEAR STEINER TREES

DOI10.1142/S021819590700232XzbMath1121.68088OpenAlexW2096702260WikidataQ57013280 ScholiaQ57013280MaRDI QIDQ5297794

Anna Schulze, Matthias Müller-Hannemann

Publication date: 13 July 2007

Published in: International Journal of Computational Geometry & Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s021819590700232x

zbMATH Keywords

VLSI designNP-completenessSteiner treespolynomial time approximation schemeblockagesoctilinear routing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (3)

THE UNIFORM ORIENTATION STEINER TREE PROBLEM IS NP-HARD ⋮ COMPUTING THE STRETCH FACTOR AND MAXIMUM DETOUR OF PATHS, TREES, AND CYCLES IN THE NORMED SPACE ⋮ A near linear time approximation scheme for Steiner tree among obstacles in the plane

Cites Work

• Canonical forms and algorithms for Steiner trees in uniform orientation metrics
• Minimum Networks in Uniform Orientation Metrics
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• An Approximation Scheme for Finding Steiner Trees with Obstacles
• Reducing the Steiner Problem in a Normed Space
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• The Complexity of Computing Steiner Minimal Trees
• Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
• Reducing the Steiner problem in four uniform orientations
• On Steiner’s Problem with Rectilinear Distance

This page was built for publication: HARDNESS AND APPROXIMATION OF OCTILINEAR STEINER TREES