高文宇,李绍华.图的树分解及其算法应用研究进展[J].计算机科学,2012,39(3):14-18
图的树分解及其算法应用研究进展
Tree Decomposition and its Applications in Algorithms:Survey
  
DOI:
中文关键词:  图子式,树宽,树分解,参数算法,近似算法
英文关键词:Graph minor, Tree width, Tree decomposition, Parameterized algorithm, Approximation algorithm
基金项目:
作者单位
高文宇,李绍华 (广东商学院信息学院 广州510320) 
摘要点击次数: 6238
全文下载次数: 1511
中文摘要:
      图的树宽和树分解是图子式理论中发展起来的两个重要概念。图的树分解由于其本身的特性使得它在算法设计中有着极其重要的意义。从图的树宽特性、图的树分解算法、图的树分解在复杂算法问题求解中的应用等方面对近年来的相关研究进展做了深入的分析和介绍,结合一些简洁的实例分析了一些重要的原理和方法,讨论了其中的一些问题,并给出了今后的一些研究方向。
英文摘要:
      Tree width and tree decomposition arc 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.
查看全文  查看/发表评论  下载PDF阅读器