On minimum generalized Manhattan connections

DOI10.1007/978-3-030-83508-8_7MaRDI QIDQ832842zbMATH OpenOpenAlexFDO

Authors Margarita Capretto, Parinya Chalermsook, Christoph Damerius, Peter Kling, Lukas Nölke, Nidia Obscura Acosta, Joachim Spoerhase, Antonios Foivos Antoniadis

Publication date 25 March 2022

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

zbMATH Keywords

NP-hardnessbinary search treeManhattan networks

Mathematics Subject Classification ID

Data structures (68P05) Algorithms in computer science (68Wxx)

Cites work

• A Fast 2-Approximation Algorithm for the Minimum Manhattan Network Problem
• A rounding algorithm for approximating minimum Manhattan networks
• Algorithmic graph theory and perfect graphs
• Approximating a minimum Manhattan network
• Approximating the generalized minimum Manhattan network problem
• Design networks with bounded pairwise distance
• Dynamic Optimality—Almost
• Improved approximation algorithms for directed Steiner forest
• Minimum Manhattan network is NP-complete
• On the Dynamic Finger Conjecture for Splay Trees. Part II: The Proof
• Self-adjusting binary search trees
• Self-adjusting binary search trees: what makes them tick?
• Set connectivity problems in undirected graphs and the directed Steiner network problem
• The geometry of binary search trees
• Weighted dynamic finger in binary search trees

This page was built for publication: On minimum generalized Manhattan connections

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