Branch-decomposition of Graphs and Its Algorithmic Applications

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

• 批准号: 250304-2012
• 负责人: Gu, Qianping
• 金额: $ 2.04万
• 依托单位: Simon Fraser University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2013
• 资助国家: 加拿大
• 起止时间: 2013-01-01 至 2014-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=525007
• 关键词: 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困难问题的实际有效算法。研究结果有望为解决这些问题建立新的方法，并提高优化工具的性能。我们期望在拟议的研究中创造的知识将转移到加拿大和世界范围的学术界和工业界，对解决实际中的图形难题的研究和开发产生重大影响。