Branch-decomposition of Graphs and Its Algorithmic Applications

图的分支分解及其算法应用

• 批准号: 250304-2012
• 负责人: Gu, Qianping
• 金额: $ 2.04万
• 依托单位: Simon Fraser University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2015
• 资助国家: 加拿大
• 起止时间: 2015-01-01 至 2016-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=570882
• 关键词: Branch; decomposition; Graphs; Its; Algorithmic

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.

图是用于计算，优化和网络的良好模型。例如，可以将许多资源分配问题建模为图中的主导问题，通信网络中的通道分配问题作为图顶点着色问题以及网络中的路由问题作为图形中的脱节路径问题。具有宽阔和重要应用的图表中的许多问题（包括上述这些应用程序）都是NP-HARD。在许多应用中，提供最佳的NP硬性问题解决方案的确切算法非常重要。最近，基于图形分类的概念，朝着图中NP硬性问题的精确算法取得了显着的理论进步。但是，使这些算法实用仍然存在挑战。这项研究的目的是消除这些障碍，以根据分支分解的概念来开发图形中NP问题的实际有效算法。该研究的结果有望建立解决这些问题并提高优化工具的性能的新方法。我们预计，拟议的研究中创建的知识将转移到加拿大和全球的学术界和行业，以对解决实践中图表中的硬性问题的研究和发展产生重大影响。