Publication:2258071

DOI10.1007/s00453-013-9778-zzbMath1308.68152arXiv1107.0901OpenAlexW2571356654MaRDI QIDQ2258071

Joachim Spoerhase, Aparna Das, Michael Kaufmann, Alexander Wolff, Stephen G. Kobourov, Emden R. Gansner

Publication date: 2 March 2015

Published in: Algorithmica, Algorithms – ESA 2011 (Search for Journal in Brave)

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

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

On minimum generalized Manhattan connections ⋮ Minimum Manhattan network problem in normed planes with polygonal balls: a factor 2.5 approximation algorithm ⋮ Approximating the generalized minimum Manhattan network problem ⋮ Approximating minimum Manhattan networks in higher dimensions ⋮ Optimal realizations and the block decomposition of a finite metric space

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Improved approximation algorithms for directed Steiner forest
• Minimum Manhattan network is NP-complete
• A series of approximation algorithms for the acyclic directed Steiner tree problem
• Approximation schemes for NP-hard geometric optimization problems: a survey
• Polynomial time approximation scheme for the rectilinear Steiner arborescence problem
• Approximating minimum Manhattan networks in higher dimensions
• The minimum Manhattan network problem: Approximations and exact solutions
• A rounding algorithm for approximating minimum Manhattan networks
• Jump Number of Two-Directional Orthogonal Ray Graphs
• GREEDY CONSTRUCTION OF 2-APPROXIMATE MINIMUM MANHATTAN NETWORKS
• The Minimal Manhattan Network Problem in Three Dimensions
• Approximation Algorithms for Directed Steiner Problems
• Algorithms and Computation