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

这个为期两年的奖项支持俄勒冈大学的Andrzej 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.