Approximating minimum Manhattan networks in higher dimensions
From MaRDI portal
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
Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)
Related Items (5)
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
This page was built for publication: Approximating minimum Manhattan networks in higher dimensions
