Paper at ICALP 2015 on temporal graph exploration

Erlebach, Hoffmann and Kammer (a collaborator from University of Augsburg) have published a paper at ICALP 2015 about temporal graph exploration. For graphs that change over time, they consider the problem of finding a temporal walk that visits all vertices and has the earliest arrival time. They give a strong inapproximability result for general temporal graphs and establish various upper bounds on the exploration schedule length for restricted classes of graphs.

A preprint of an extended version is available here: arXiv:1504.07976 [cs.DS]

Filed under:

Share this page: