A $$(1+{\varepsilon })$$ ( 1 + ε ) -Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs
From MaRDI portal
Publication:3448808
DOI10.1007/978-3-662-47672-7_38zbMath1398.68671arXiv1502.04588MaRDI QIDQ3448808
Ian Post, Jochen Könemann, Wai Shing Fung, Andreas Emil Feldmann
Publication date: 27 October 2015
Published in: Automata, Languages, and Programming (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1502.04588
90C35: Programming involving graphs or networks
68Q25: Analysis of algorithms and problem complexity
90B06: Transportation, logistics and supply chain management
68W25: Approximation algorithms
Related Items
Active Nearest-Neighbor Learning in Metric Spaces, Polynomial-Time Approximation Schemes for k-center, k-median, and Capacitated Vehicle Routing in Bounded Highway Dimension, The Parameterized Hardness of the k-Center Problem in Transportation Networks, Approximation Schemes for Capacitated Vehicle Routing on Graphs of Bounded Treewidth, Bounded Doubling, or Highway Dimension, Fixed-parameter approximations for \(k\)-center problems in low highway dimension graphs, On the VC-dimension of unique round-trip shortest path systems, Fixed Parameter Approximations for k-Center Problems in Low Highway Dimension Graphs
Uses Software
Cites Work
- 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
- 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
- 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
- The traveling salesman problem
- A tight bound on approximating arbitrary metrics by tree metrics