A $(1+\varepsilon)$-Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs
From MaRDI portal
Publication:5376438
DOI10.1137/16M1067196zbMath1398.68672OpenAlexW2952768305MaRDI QIDQ5376438
Andreas Emil Feldmann, Jochen Könemann, Ian Post, Wai Shing Fung
Publication date: 18 September 2018
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/16m1067196
Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Transportation, logistics and supply chain management (90B06) Approximation algorithms (68W25)
Related Items (6)
Generalized \(k\)-center: distinguishing doubling and highway dimension ⋮ On the VC-dimension of unique round-trip shortest path systems ⋮ Travelling on graphs with small highway dimension ⋮ Computing a Minimum-Cost k-Hop Steiner Tree in Tree-Like Metrics ⋮ On Hop-Constrained Steiner Trees in Tree-Like Metrics ⋮ Computing Constrained Shortest-Paths at Scale
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Approximation schemes for NP-hard geometric optimization problems: a survey
- On the history of the Euclidean Steiner tree problem
- Approximating TSP on Metrics with Bounded Global Growth
- VC-Dimension and Shortest Path Algorithms
- Fast Routing in Road Networks with Transit Nodes
- Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
- Highway Dimension and Provably Efficient Shortest Path Algorithms
- Locational analysis: highlights of growth to maturity
- Approximation Algorithms for Metric Facility Location Problems
- Fixed Parameter Approximations for k-Center Problems in Low Highway Dimension Graphs
- A Linear-Time Approximation Scheme for TSP in Undirected Planar Graphs with Edge-Weights
- Bypassing the embedding
- Graph minors. II. Algorithmic aspects of tree-width
- Greedy Strikes Back: Improved Facility Location Algorithms
- Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
- Beyond Highway Dimension: Small Distance Labels Using Tree Skeletons
- Cops, robbers, and threatening skeletons
- On the History of Combinatorial Optimization (Till 1960)
- Search-Space Size in Contraction Hierarchies
- The traveling salesman problem
- Algorithms – ESA 2004
- In Pursuit of the Traveling Salesman
- A tight bound on approximating arbitrary metrics by tree metrics
This page was built for publication: A $(1+\varepsilon)$-Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs
