This research project in theoretical computer science 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 area. 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. Three problems concerning graphs are being investigated: (1) balancing competing demands. An example is finding a spanning tree of a graph subject to balancing mutually contending terms in the objective function. (2)The sensitivity of algorithmic solutions to changes in the problem input. (3) Search strategies for relocatable objects in graphs. In addition, the project investigates data structures for dynamic maintaining of information about graphs.
