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

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

Mathematics Subject Classification ID

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

• 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