Properties of Graphs With Bounded Highway Dimension
| Speaker: | Andreas Feldmann |
|---|---|
| Affiliation: | University of Waterloo |
| Room: | Mathematics 3 (M3) 2134 |
Abstract:
The "highway dimension" (hd) of a graph was defined by Abraham et al. in 2010, in order to model transportation networks. In particular, a road network can be modelled as a graph with bounded hd. They show that this property can explain the good behaviour of certain shortest path heuristics. In recent work together with Isaac Fung, Jochen Könemann, and Ian Post, we further investigate the properties of this graph class. In particular, we are interested in other problems that typically arise on transportation networks, such as constructing sparse spanners, or solving the travelling salesman problem (TSP). In this talk I will focus on the properties of bounded hd graphs, and give a rough outline of how these properties lead to solutions to our considered problems.