This two-year award supports U.S.-Sweden cooperative research in computer and computation theory between Andrzej Proskurowski of the University of Oregon and Stefan Arnborg of the Royal Institute of Technology, Stockholm, Sweden. The principal objective of this project is the development of efficient algorithms for hard optimization problems restricted to partial k- trees. The class of partial k-trees includes most of the important families of graphs with an underlying tree structure. This research focuses on the practical aspects of recognizing partial k-trees and finding tree representations. Dr. Proskurowski brings to this collaboration his expertise in algorithmic graph theory. This is complemented by Dr. Arnborg's background in logic. They propose to address deficiencies in current graph theory through their work on a graph reduction system, including implementation of related algorithms, and by establishing algorithms for obstruction sets. They will also investigate the streamlining of algorithms in solving distance-related discrete optimization problems. Their combined and complementary expertise and efforts could lead to new, fast, practical algorithms for difficult optimization problems.
