  In the recent research of data mining, frequent structures in a sequence of
graphs have been studied intensively, and one of the main concern is changing
structures along a sequence of graphs that can capture dynamic properties of
data. On the contrary, we newly focus on "preserving structures" in a graph
sequence that satisfy a given property for a certain period, and mining such
structures is studied. As for an onset, we bring up two structures, a connected
vertex subset and a clique that exist for a certain period. We consider the
problem of enumerating these structures. and present polynomial delay
algorithms for the problems. Their running time may depend on the size of the
representation, however, if each edge has at most one time interval in the
representation, the running time is O(|V||E|^3) for connected vertex subsets
and O(min{\Delta^5, |E|^2\Delta}) for cliques, where the input graph is G =
(V,E) with maximum degree \Delta. To the best of our knowledge, this is the
first approach to the treatment of this notion, namely, preserving structures.

Data Structures and Algorithms;Discrete Mathematics