Skip to content

Thursday 11:30 – Ben Bumpus

Exploring temporal graphs: introducing interval-membership-width.

Traditionally, one way of coping with computational intractability is to restrict inputs to some class which displays algorithmically exploitable structure. For problems on graphs, there is a vast literature on how to do this. However, real-world networks often cannot be realistically modelled as graphs since they are not static. Indeed, many networks change over time and their edges may appear or disappear (for instance friendships may change in a social network). Such networks are called temporal graphs.
Unfortunately, current algorithmic techniques are often of little use on temporal graphs since many problems on these inputs are intractable even when their topology is severely restricted (such as being a temporal tree or even a star). Thus, to be able to define algorithmically useful notions of `temporal structure’, we need notions that take temporal information into account. In this talk, I will introduce such a measure (called interval-membership-width) and explain its relevance to algorithmic problems on temporal graphs.