Branch-decomposition of Graphs and Its Algorithmic Applications

点击翻译按钮获取中文摘要

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.