Approximating the generalized minimum Manhattan network problem

DOI10.1007/S00453-017-0298-0MaRDI QIDQ1751089zbMATH OpenOpenAlexFDO

Authors Aparna Das, Krzysztof Fleszar, Joachim Spoerhase, Sankar Veeramoni, Alexander Wolff, 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)

Recommendations

• Approximating the generalized minimum Manhattan network problem
• Dynamic programming approach to the generalized minimum Manhattan network problem
• Dynamic programming approach to the generalized minimum Manhattan network problem

Cites work

• scientific article; zbMATH DE number 1839431 (Why is no real title available?)
• A fixed-parameter algorithm for the minimum Manhattan network problem
• A rounding algorithm for approximating minimum Manhattan networks
• Almost optimal set covers in finite VC-dimension
• Approximating a minimum Manhattan network
• Approximating the generalized minimum Manhattan network problem
• Approximation schemes for NP-hard geometric optimization problems: a survey
• Cost-minimal trees in directed acyclic graphs
• Geometric Spanner Networks
• Greedy construction of 2-approximate minimum Manhattan networks
• Improved approximation algorithms for directed Steiner forest
• Minimum Manhattan network is NP-complete
• On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems
• Polynomial time approximation scheme for the rectilinear Steiner arborescence problem
• Small-size ε-nets for axis-parallel rectangles and boxes
• The Minimal Manhattan Network Problem in Three Dimensions
• The Rectilinear Steiner Arborescence Problem Is NP-Complete
• The rectilinear Steiner arborescence problem

Cited in

(10)

• Linear-size planar Manhattan network for convex point sets
• On minimum generalized Manhattan connections
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• The Minimum Manhattan Network Problem: A Fast Factor-3 Approximation
• Approximating the generalized minimum Manhattan network problem
• A PTAS for the horizontal rectangle stabbing problem
• A PTAS for the horizontal rectangle stabbing problem
• scientific article; zbMATH DE number 7561415 (Why is no real title available?)
• Dynamic programming approach to the generalized minimum Manhattan network problem
• Dynamic programming approach to the generalized minimum Manhattan network problem

This page was built for publication: Approximating the generalized minimum Manhattan network problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1751089)