Branch-decomposition of Graphs and Its Algorithmic Applications

图是计算、优化和网络的常用模型。例如，许多资源分配问题可以建模为图中的支配问题，通信网络中的信道分配问题可以建模为图的顶点着色问题，网络中的路由问题可以建模为图中的不相交路径问题。在具有广泛和重要应用的图中，许多问题是NP难的，包括上面提到的这些问题。给出NP-Hard问题最优解的精确算法在许多应用中具有重要意义。近年来，基于图的分支分解的概念，在图的NP-Hard问题的精确算法方面取得了重大的理论进展。然而，要使这些算法实用化，仍然存在挑战。这项研究的目的是消除这些障碍，基于分支分解的概念，开发出实用有效的算法来解决图中的NP-Hard问题。这项研究的结果有望为解决这些问题建立新的方法，并提高优化工具的性能。我们期望，在拟议的研究中创造的知识将转移到加拿大和世界各地的学术界和工业界，对解决实际中的图中难题的研究和开发产生重大影响。

Graphs are well used models for computation, optimization and networks. For example, many resource allocation problems can be modeled as domination problems in graphs, channel assignment problems in communication networks as graph vertex coloring problems, and routing problems in networks as disjoint paths problems in graphs. Many problems in graphs with wide and important applications, including these mentioned above, are NP-hard. Exact algorithms which give optimal solutions of NP-hard problems are of great importance in many applications. Recently, based on the notion of branch-decompositions of graphs, there has been significant theoretical progress towards exact algorithms for NP-hard problems in graphs. However, there are still challenges to make those algorithms practical. The goal of this research is to remove those barriers to develop practically efficient algorithms for NP-hard problems in graphs based on the notion of branch-decompositions. The outcome of the research is expected to establish new approaches for solving these problems and to improve the performance for the optimization tools. We expect that the knowledge created in the proposed research will be transferred to Canadian and world-wide academia and industry to produce significant impact on the research and development for solving hard problems in graphs in practice.