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 困难的。给出 NP 困难问题最优解的精确算法在许多应用中非常重要。最近，基于图的分支分解的概念，在图的 NP 难问题的精确算法方面取得了重大的理论进展。然而，使这些算法实用仍然存在挑战。本研究的目标是消除这些障碍，基于分支分解的概念，为图中的 NP 难题开发实用有效的算法。研究成果有望建立解决这些问题的新方法并提高优化工具的性能。我们期望拟议研究中创造的知识将转移到加拿大和世界各地的学术界和工业界，对解决实践中图形难题的研究和开发产生重大影响。