Graph theory seminar - Andreas FeldmannExport this event to calendar

Wednesday, June 18, 2014 — 3:30 PM EDT

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.

Location 
M3 - Mathematics 3
2134
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

S M T W T F S
29
30
31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
1
2
  1. 2021 (102)
    1. December (2)
    2. November (7)
    3. October (6)
    4. September (12)
    5. August (6)
    6. July (10)
    7. June (12)
    8. May (7)
    9. April (9)
    10. March (13)
    11. February (8)
    12. January (10)
  2. 2020 (119)
    1. December (5)
    2. November (12)
    3. October (12)
    4. September (12)
    5. August (11)
    6. July (17)
    7. June (11)
    8. May (6)
    9. March (11)
    10. February (11)
    11. January (11)
  3. 2019 (167)
  4. 2018 (136)
  5. 2017 (103)
  6. 2016 (137)
  7. 2015 (136)
  8. 2014 (88)
  9. 2013 (48)
  10. 2012 (39)
  11. 2011 (36)
  12. 2010 (40)
  13. 2009 (40)
  14. 2008 (39)
  15. 2007 (15)