Almost every scientific domains, including mathematics, computer science, chemistry, and biology, can be modeled and studied by graphs. We try to keep the descriptions consistent as much as possible and we hope the survey can help practitioners to understand existing time-dependent techniques.Ī graph is a data structure which is widely used in network modeling. We also introduce existing time-dependent systems and summarize their advantages and limitations. In addition, we review some classic problems on time-dependent graphs, e.g., route planning, social analysis, and subgraph problem (including matching and mining). In this paper, we discuss the definition and topological structure of time-dependent graphs, as well as models for their relationship to dynamic systems. Though static graphs have been extensively studied, for their time-dependent generalizations, we are still far from a complete and mature theory of models and algorithms. In particular, the time-dependent graph is a very broad concept, which is reflected in the related research with many names, including temporal graphs, evolving graphs, time-varying graphs, historical graphs, and so on. Many real-life scenarios can be better modeled by time-dependent graphs, such as bioinformatics networks, transportation networks, and social networks. In such graphs, the weights associated with edges dynamically change over time, that is, the edges in such graphs are activated by sequences of time-dependent elements.
A time-dependent graph is, informally speaking, a graph structure dynamically changes with time.
0 kommentar(er)
