A fixed-parameter algorithm for the minimum Manhattan network problem

MaRDI QIDQ2968082zbMATH OpenFDO

Authors Christian Knauer, Andreas Spillner

Publication date 9 March 2017

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• scientific article; zbMATH DE number 1979512
• Approximating a minimum Manhattan network
• A Fast 2-Approximation Algorithm for the Minimum Manhattan Network Problem
• Minimum Manhattan network is NP-complete
• Minimum Manhattan network is NP-complete

Cited in

(8)

• Linear-size planar Manhattan network for convex point sets
• Minimum Manhattan network is NP-complete
• The Minimum Manhattan Network Problem: A Fast Factor-3 Approximation
• Approximating the generalized minimum Manhattan network problem
• Searching for realizations of finite metric spaces in tight spans
• Minimum Manhattan network is NP-complete
• The Minimal Manhattan Network Problem in Three Dimensions
• An algorithm for generating minimum cost network flow problems with specific structure and known optimal solutions

This page was built for publication: A fixed-parameter algorithm for the minimum Manhattan network problem

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