On-Line Problems in Graphs and Sets

联机问题出现在许多重要的实际环境中，例如操作系统、编程语言实现和机器人。这些问题涉及必须动态处理的请求序列。该项目的目标是找到快速算法并证明集和图在线问题的下界，这两个基本的数学对象用于模拟无数的计算机应用程序。该项目将调查逻辑编程中出现的问题，并涉及不同的变量集。它还将研究维护在线变化的图形信息的问题。这种变化的图形模型在电路仿真、网络和分布式计算中的应用。解决在线问题涉及动态数据结构的开发，动态数据结构是快速访问和修改存储信息的复杂工具。动态数据结构通常用于计算机科学的其他领域。该项目的最终目标是调查某些集和图的在线问题是否固有地困难。该项目将提高对与实际问题相关的理论问题的理解，并有望为这些问题提供更好的解决方案。

On-line problems arise in many important, practical settings, such as operating systems, programming language implementations, and robotics. These problems involve sequences of requests that must be processed on the fly. The goal of the project is to find fast algorithms and to prove lower bounds for on-line problems in sets and graphs, two fundamental mathematical objects that are used to model a myriad of computer applications. The project will investigate problems which arise in logic programming and that involve varying sets of variables. It will also study problems of maintaining information about graphs that are changing on-line. Such changing graphs model applications in circuit simulation, networks, and distributed computing. Solving on-line problems involves the development of dynamic data structures, which are sophisticated tools for quickly accessing and modifying stored information. Dynamic data structures often have uses in other areas of computer science. A final goal of the project is to investigate whether certain on-line problems in sets and graphs are inherently difficult. The project will improve the understanding of theoretical issues relevant to practical problems, and hopefully give better solutions to those problems.