ProbleMS on Temporal Graphs

Abstract

The idea of temporal graphs can be thought of as a recent addition to the extensively researched concept of graph theory. The advent of cheap wireless communication devices and need of efficient communication protocols, in addition to distributed computation networks has motivated progress in this field. However, the temporal analogues to polynomial time problem on static graphs are very often NP-hard. Thus, there seem to a lot of problems which can be parameterized and explored under various constraints. The study of temporal graphs by parameterized algorithms is a field which is still very much in its infancy, and only a few basic properties and problems have been defined in literature. In this document, we will explore the problem of finding temporal paths parameterized by their length, and a few temporal walk-related problems.