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.