权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Algorithmic Aspects of Temporal Graphs

时间图的算法方面

基本信息

批准号：
EP/P020372/1
负责人：
George Mertzios
金额：
$ 40.66万
依托单位：
Durham University
依托单位国家：
英国
项目类别：
Research Grant
财政年份：
2017
资助国家：
英国
起止时间：
2017 至无数据
项目状态：
已结题

来源：
https://gtr.ukri.org/projects?ref=EP%2FP020372%2F1
关键词：
Algorithmic Aspects Temporal Graphs

项目摘要

The design and analysis of algorithms on graphs is a major sub-discipline of Computer Science. Graphs (composed of vertices and edges) are ubiquitous not only in Computer Science and Mathematics but across the whole spectrum of Science and Engineering. They are used to abstractly model diverse real world systems, where vertices and edges represent elementary system units and some kind of interactions between them, respectively. However, in modern systems this modeling paradigm using static graphs may be restrictive or oversimplifying, as the interactions usually change over time in a highly dynamic manner. For example, friendships are added and removed over time in a social network and links in a communication network may change dynamically, either according to a specific known pattern (satellites following a trajectory) or in an unpredictable manner (mobile ad hoc networks). The common characteristic in all these application areas is that the system structure, i.e. graph topology, is subject to discrete changes over time.A temporal graph consists of an underlying graph and a time-labeling function that assigns to every edge of the graph a set of discrete time-labels. These time-labels are drawn from the set of natural numbers, indicating the discrete time points where the corresponding edge is present. The conceptual shift from static to temporal graphs has a significant impact on the definition of the basic graph parameters and metrics, and thus also on the type of tasks that can be performed. Graph properties can be generally classified into a-temporal (i.e. satisfied at every time point) and temporal ones (i.e. satisfied over time). For example, although global connectivity may not hold at any single time point, communication routes may still exist over time between each pair of nodes. In particular, a path in the underlying (static) graph G is called temporal if there exists an increasing sequence of time-labels as one walks along the edges of the path.Classic metrics from static graph theory can usually be generalized in various ways to natural metrics in temporal graphs. For example, depending on the application domain, the temporal analogue of a ``shortest path'' between two vertices u,v can be translated as (a) the topologically shortest path, having the smallest number of edges, (b) the fastest path, having the smallest time duration, or (c) the foremost path, arriving as early as possible (regardless of the starting time). The computational complexity of a static graph problem may or may not carry over to its temporal counterpart; this strongly depends on the problem and the metric concerned. It is known that a shortest / fastest / foremost temporal path can be computed in polynomial time; however, computing strongly connected components is NP-complete in temporal graphs, in contrast to the static case. Although some temporal graph optimization problems may be hard to solve or to approximate in the worst case, an optimal solution may be efficiently computable when we restrict in the input temporal graph (a) its underlying topology, or (b) the time-labeling, i.e. the temporal pattern in which the time-labels appear, or both. Restricting the input temporal pattern is a distinguishing temporal aspect with no immediate analogue in static graphs.Within the proposed research we plan to investigate the various temporal graph problems, as well as to more deeply understand their underlying combinatorial structure. In addition to temporal path-related problems, we plan to systematically study how the notion of time can be appropriately introduced to non-path graph problems (such as temporal covering and temporal coloring problems) and to explore the computational complexity landscape of these new problems. Our over-arching goal is to develop an algorithmic temporal graph theory, similar to the algorithmic graph theory on static graphs, taking into account the inherent presence of the time dimension.

图上算法的设计和分析是计算机科学的一个主要分支学科。图（由顶点和边组成）不仅在计算机科学和数学中无处不在，而且在整个科学和工程领域都是如此。它们被用来抽象不同的真实的世界系统的模型，其中顶点和边分别表示基本的系统单元和它们之间的某种相互作用。然而，在现代系统中，这种使用静态图的建模范例可能是限制性的或过于简化的，因为交互通常以高度动态的方式随时间变化。例如，在社交网络中随着时间的推移添加和移除友谊，并且通信网络中的链接可以根据特定的已知模式（遵循轨迹的卫星）或者以不可预测的方式（移动的自组织网络）动态地改变。所有这些应用领域的共同特点是系统结构（即图拓扑）随时间离散变化。时态图由底层图和时间标签函数组成，时间标签函数为图的每条边分配一组离散的时间标签。这些时间标签是从自然数集合中提取的，指示存在相应边缘的离散时间点。从静态图到时态图的概念转变对基本图参数和度量的定义产生了重大影响，因此也对可以执行的任务类型产生了重大影响。图形属性通常可以分为时间属性（即在每个时间点满足）和时间属性（即随时间满足）。例如，尽管全球连通性可能不在任何单个时间点保持，但是通信路由可能仍然随时间存在于每对节点之间。特别地，在底层（静态）图G中的路径被称为时态的，如果当沿着路径的边缘沿着行走时存在递增的时间标签序列。静态图论中的经典度量通常可以以各种方式推广到时态图中的自然度量。例如，取决于应用领域，两个顶点u、v之间的"最短路径“的时间模拟可以被转换为（a）拓扑最短路径，具有最小的边数，（B）最快路径，具有最小的持续时间，或（c）最前面的路径，尽可能早地到达（不管起始时间）。静态图问题的计算复杂性可能会或可能不会延续到其时间对应物;这在很大程度上取决于问题和相关度量。众所周知，最短/最快/最重要的时间路径可以在多项式时间内计算;然而，与静态情况相比，计算强连通分量在时间图中是NP完全的。虽然在最坏的情况下，一些时间图优化问题可能难以解决或近似，但是当我们在输入时间图中限制（a）其底层拓扑或（B）时间标签（即，时间标签出现的时间模式）或两者时，最优解可以是可有效计算的。限制输入的时间模式是一个显着的时间方面，没有直接的模拟在静态graphs.Within拟议的研究，我们计划调查的各种时间图的问题，以及更深入地了解其潜在的组合结构。除了时间路径相关的问题，我们计划系统地研究如何将时间的概念适当地引入非路径图问题（如时间覆盖和时间着色问题），并探索这些新问题的计算复杂性。我们的目标是开发一个算法的时间图论，类似于静态图的算法图论，考虑到时间维度的固有存在。