AF:Small:Data Structures for Dynamic Networks

物理网络（如通信网络和道路网络）是动态对象，容易发生突然故障、拥塞和恶意攻击。尽管如此，我们必须能够计算这些网络当前状态的基本功能，即，当网络组件故障和恢复时，我们需要动态算法和数据结构沿最短路径路由，并计算距离，流量/切割容量和点对点连接。目前部署的系统通常通过从头开始周期性地重新计算所有感兴趣的网络属性来处理瞬态故障问题。这种解决方案在两个方面是不够的。它们在计算上效率低下，其程度取决于给定的网络属性，并且它们不能动态响应网络组件故障。这个项目的技术目标是双重的。首先是沿着仙人掌树和Gomory-Hu树的思路，开发图形和图形属性的抽象表示。这些图形表示在高效算法和数据结构的设计中很有用，但也对更广泛的数学界感兴趣。二是建立动态子图模型和d-失效模型中的数据结构。这些抽象模型捕获了许多现实世界应用程序中的情况：有一个固定的基板网络，可以通过可能效率低下的算法提前处理，这受到一系列节点/链接故障和恢复与查询混合在一起的影响。该项目的一个普遍主题是通过接受近似解决方案来确定可以获得的效率收益（在运行时间，空间消耗方面），例如，保证精确到某些固定的乘法或加法误差的近似最短路线或近似最小切割。除了其具体的研究目标之外，这个项目的目的是(i)培养本科生和研究生设计和严格分析有效数据结构的能力，以及（ii）通过开发适合研究生或高级本科生的课程材料，将现代数据结构纳入计算机科学课程。

Physical networks (such as communications networks and road networks) are dynamic objects, prone to sudden failures, congestion, and malicious attacks. Nonetheless, we must be able to compute basic functions of the current state of these networks, i.e., as network components fail and recover, we need dynamic algorithms and data structures to route along shortest paths and to calculate distances, flow/cut capacities, and point-to-point connectivity. Currently deployed systems typically deal with the problem of transient failures by periodically recomputing from scratch all the network properties of interest. Solutions of this type are insufficient in two ways. They are computationally inefficient, the extent to which depends on the given network property, and they do not respond to network component failures dynamically.The technical aims of this project are two-fold. The first is to develop abstract representations of graphs and graph properties, along the lines of cactus trees and Gomory-Hu trees. These graph representations are useful in the design of efficient algorithms and data structures, but are also of interest to the broader mathematics community. The second is to develop data structures in the dynamic subgraph model and d-failure model. These abstract models capture the situation found in many real world applications: there is a fixed substrate network, which can be processed in advance by possibly inefficient algorithms, which is subject to a sequence of node/link failures and recoveries intermixed with queries. A pervasive theme of the project is to determine what gains in efficiency can be had (in running time, space consumption) by accepting approximate solutions, e.g., approximately shortest routes or approximately minimum cuts that are guaranteed to be accurate up to some fixed multiplicative or additive error.In addition to its specific research goals, the aims of this project are to (i) train undergraduate and graduate students in the design and rigorous analysis of efficient data structures, and (ii) incorporate modern data structures into the computer science curriculum by developing course materials appropriate to students atthe graduate or advanced undergraduate level.