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.