U.S.-Sweden Cooperative Research: Graphs with Bounded Treewidth and Complexity of Restricted Discrete OptimizationProblems

这个为期两年的奖项支持美国-瑞典合作研究 在计算机和计算理论方面， 俄勒冈州大学的Proskurowski和密歇根大学的Stefan Arnborg 瑞典斯德哥尔摩的皇家理工学院。 的 该项目的主要目标是开发高效的 算法的硬优化问题限制到部分k- 树 部分k树的类包括大多数重要的 具有底层树结构的图族。本研究 侧重于识别部分k树的实际方面， 寻找树的代表。 Proskurowski博士为这次合作带来了他的专业知识， 算法图论 这是由博士补充。 阿恩伯格的逻辑背景。他们建议解决 当前图论的不足之处，通过他们的工作， 图形归约系统，包括相关的实现 算法，并通过建立算法的障碍集。 他们还将调查算法的精简， 解决距离相关的离散优化问题。 他们的 结合和互补的专门知识和努力， 新的，快速的，实用的算法困难的优化问题。

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.