AF:Small:Data Structures for Dynamic Networks

点击翻译按钮获取中文摘要

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.