Minimum Manhattan network is NP-complete

DOI10.1145/1542362.1542429zbMath1388.68287OpenAlexW2092424636MaRDI QIDQ5370740

Zeyu Guo, He Sun, Francis Y. L. Chin

Publication date: 20 October 2017

Published in: Proceedings of the twenty-fifth annual symposium on Computational geometry (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/10722/145068

zbMATH Keywords

NP-complete3-SATminimum Manhattan network

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) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (1)

Searching for realizations of finite metric spaces in tight spans

This page was built for publication: Minimum Manhattan network is NP-complete