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 goals are to generate improved techniques, and characterize significant complexity relationships.
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.
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. This approach can be adapted for use 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.