Hierarchy of Transportation Network Parameters and Hardness Results

DOI10.4230/LIPIcs.IPEC.2019.4OpenAlexW2997816837MaRDI QIDQ5875536

Johannes Blum

Publication date: 3 February 2023

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

zbMATH Keywords

\(k\)-centergraph parametershighway dimensionskeleton dimension

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithms in computer science (68Wxx) Parameterized complexity, tractability and kernelization (68Q27)

Related Items

Computing L(p,1)-Labeling with Combined Parameters, The parameterized hardness of the \(k\)-center problem in transportation networks, Generalized \(k\)-center: distinguishing doubling and highway dimension, Unnamed Item, Polynomial time approximation schemes for clustering in low highway dimension graphs, Sublinear search spaces for shortest path planning in grid and road networks, Computing \(L(p, 1)\)-labeling with combined parameters, Travelling on graphs with small highway dimension, \(\mathsf{W[1}\)-hardness of the \(k\)-center problem parameterized by the skeleton dimension]