图的树分解及其算法应用研究进展  

Tree Decomposition and its Applications in Algorithms:Survey

作　　者：高文宇[1] 李绍华[1] 

机构地区：[1]广东商学院信息学院,广州510320

出　　处：《计算机科学》2012年第3期14-18,共5页Computer Science

基　　金：广东省自然科学基金(8151032001000013)资助

摘　　要：图的树宽和树分解是图子式理论中发展起来的两个重要概念。图的树分解由于其本身的特性使得它在算法设计中有着极其重要的意义。从图的树宽特性、图的树分解算法、图的树分解在复杂算法问题求解中的应用等方面对近年来的相关研究进展做了深入的分析和介绍,结合一些简洁的实例分析了一些重要的原理和方法,讨论了其中的一些问题,并给出了今后的一些研究方向。Tree width and tree decomposition are two important concepts developed by graph minor theory. Because of its own characteristics, tree decomposition plays an important role in algorithm design. The tree width of graph, tree decomposition algorithm,applications of tree decomposition algorithm for problem solving in a complex problems were deeply analysed. Three aspects of the related research in recent years were given a thorough analysis and presentation, and a number of important principles and methods were presented by some simple examples. Furthermore, a few future research issues were outlined.

关 键 词：图子式 树宽 树分解 参数算法 近似算法 

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论]