Sponsor: NSF
This research project in the analysis of algorithms focuses on problems in two interrelated areas: algorithms for graph problems, and the design of data structures. The common theme is the investigation of efficient computation in these areas. The goals are to generate improved techniques, and characterize significant complexity relationships. A central issue is the efficient coordination of the acquisition of information during a complex computational task.
One of the goals of the work in graph algorithms is the modeling of problems in which the motion of a set of objects must be coordinated. Efficient algorithms for minimum-cost or near-minimum-cost motion have been found for a variety of problems, when the motion is constrained to be along the edges of relatively simple graphs.
A goal in the study of data structures has been the design of data structures that allow for the efficient manipulation of data in complex settings, and the determination of how the time requirements of such operations relate to known lower bounds. One set of results gives optimal algorithms for several unresolved problems in parametric search: partitioning a vertex-weighted tree, and finding an optimal set of supply centers in an edge-weighted tree. These results resolve problems that had been open for more than a decade.
Another goal in the study of data structures has been the design of data structures that allow for the efficient maintenance of a query structure when the underlying data is modified. One technique resulting from this research gives a fast method for maintaining information about 2-edge-connected components in an undirected graph. The technique is based on a data structure for a spanning tree of a graph, in which nodes of the graph are repeatedly clustered. An example showing a clustering and the resulting data structure is given in the accompanying figure. The data structure can be used in algorithms for many other problems, including maximum flow, minimum-cost flow, and dynamic maintenance of expression trees.
A recent focus has been on measuring the robustness of solutions to problems such as the minimum spanning tree problem. Efficient algorithms for finding exact and approximate solutions have been identified when either edge costs can be raised by a fixed amount or a fixed number of edges can be removed so as to maximize solution cost.