A $$(1+{\varepsilon })$$ ( 1 + ε ) -Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs

DOI10.1007/978-3-662-47672-7_38zbMath1398.68671arXiv1502.04588OpenAlexW2203654255MaRDI 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

Mathematics Subject Classification ID

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 (7)

Fixed Parameter Approximations for k-Center Problems in Low Highway Dimension Graphs ⋮ Approximation Schemes for Capacitated Vehicle Routing on Graphs of Bounded Treewidth, Bounded Doubling, or Highway Dimension ⋮ On the VC-dimension of unique round-trip shortest path systems ⋮ Fixed-parameter approximations for \(k\)-center problems in low highway dimension graphs ⋮ Polynomial-Time Approximation Schemes for k-center, k-median, and Capacitated Vehicle Routing in Bounded Highway Dimension ⋮ Active Nearest-Neighbor Learning in Metric Spaces ⋮ The Parameterized Hardness of the k-Center Problem in Transportation Networks

Uses Software

• DIMACS

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

This page was built for publication: A $$(1+{\varepsilon })$$ ( 1 + ε ) -Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs