Approximating the generalized minimum Manhattan network problem

DOI10.1007/s00453-017-0298-0zbMath1390.68715OpenAlexW155897563MaRDI QIDQ1751089

Joachim Spoerhase, Krzysztof Fleszar, Aparna Das, Alexander Wolff, Sankar Veeramoni, Stephen G. Kobourov

Publication date: 23 May 2018

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.377.1482

zbMATH Keywords

computational geometryapproximation algorithmsminimum Manhattan network

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Related Items

Linear-size planar Manhattan network for convex point sets ⋮ On minimum generalized Manhattan connections ⋮ A PTAS for the horizontal rectangle stabbing problem ⋮ Unnamed Item ⋮ Dynamic programming approach to the generalized minimum Manhattan network problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Improved approximation algorithms for directed Steiner forest
• Minimum Manhattan network is NP-complete
• The rectilinear Steiner arborescence problem
• Approximation schemes for NP-hard geometric optimization problems: a survey
• Polynomial time approximation scheme for the rectilinear Steiner arborescence problem
• Almost optimal set covers in finite VC-dimension
• Approximating minimum Manhattan networks in higher dimensions
• A rounding algorithm for approximating minimum Manhattan networks
• Approximating the Generalized Minimum Manhattan Network Problem
• GREEDY CONSTRUCTION OF 2-APPROXIMATE MINIMUM MANHATTAN NETWORKS
• Geometric Spanner Networks
• The Minimal Manhattan Network Problem in Three Dimensions
• On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems
• Small-size ε-nets for axis-parallel rectangles and boxes
• Cost-minimal trees in directed acyclic graphs
• The Rectilinear Steiner Arborescence Problem Is NP-Complete