Combinatorics Seminar 2015

Speaker: Irith Hartman, University of Haifa

Date: Tue, Dec 08, 2015

Time: 14:30 - 15:30

Venue: Middle Meeting Room

Title: Matchings, star partitions, and clique covers in interval graphs: Graph theoretical tools in transportation science


Analysis of GPS traces allows us to trace people’s choice of routes when travelling through the transportation network. Understanding these routes allows transportation scientists to generate route choice sets which are collections of travel options available to individual travelers in satisfying their travel demand. The recorded GPS traces reveal that people do not necessarily take the shortest or quickest path between the origin and destination points. In order to find a good route choice set generator, we enumerate all possible minimum decompositions of a given path into shortest subpaths, which corresponds to the problem of enumerating all minimum clique covers in proper interval graphs.

A second problem we will speak about is the problem of assigning people to cars in order to carpool on a daily basis. We will describe new methods in tackling this practical problem.

Slides: View slides