期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

图的树分解及其算法应用研究进展 被引量：5

Tree Decomposition and its Applications in Algorithms:Survey
在线阅读 下载PDF
导出
摘要 图的树宽和树分解是图子式理论中发展起来的两个重要概念。图的树分解由于其本身的特性使得它在算法设计中有着极其重要的意义。从图的树宽特性、图的树分解算法、图的树分解在复杂算法问题求解中的应用等方面对近年来的相关研究进展做了深入的分析和介绍,结合一些简洁的实例分析了一些重要的原理和方法,讨论了其中的一些问题,并给出了今后的一些研究方向。 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.
作者 高文宇 李绍华
机构地区 广东商学院信息学院
出处 《计算机科学》 CSCD 北大核心 2012年第3期14-18,共5页 Computer Science
基金 广东省自然科学基金(8151032001000013)资助
关键词 图子式 树宽 树分解 参数算法 近似算法 Graph minor,Tree width,Tree decomposition,Parameterized algorithm,Approximation algorithm
分类号 TP311.13 [自动化与计算机技术—计算机软件与理论]
  • 相关文献

参考文献54

  • 1Garey M R, Johnson D S. Computers and intractability: a guide to the theory of NP-eompleteness[M]. New York: W. H. Freeman & Co. ,1979.
  • 2Downey R G, Fellows M R. Parameterized Complexity[M]. New York, Springer, 1999.
  • 3Jian-ErChen.Parameterized Computation and Complexity： A New Approach Dealing with NP-Hardness[J].Journal of Computer Science & Technology,2005,20(1):18-37. 被引量：22
  • 4Robertson N, Seymour P D. Graph Minors. I. Excluding a Forest[J].Journal of Combinatorial Theory, Series B, 1983,35 : 39-61.
  • 5Robertson N, Seymour P D. Graph Minors. II. Algorithmic Aspects of Tree-Width[J]. Journal of Algorithms, 1986,7(3) : 309- 322.
  • 6Robertson N, Seymour P D. Graph Minors. III. Planar Tree- Width[J]. Journal of Combinatorial Theory, Series B, 1984,36 : 49-64.
  • 7Robertson N, Seymour P D. Graph minors. IV. Tree-width and well-quasi-ordering[J]. Journal of Combinatorial Theory, Series B, 1990,48: 227-254.
  • 8Robertson N, Seymour P D. Graph minors. X. Obstructions to tree-decomposition[J]. Journal of Combinatorial Theory, Series B, 1991,52 : 153-190.
  • 9Rohertson N, Seymour P D. Graph minors. XXI. Graphs with unique linkages[J]. Journal of Combinatorial Theory, Series B, 2009,99: 583-616.
  • 10Robertson N, Seymour P D. Graph minors. XXIII. Nash-Williams's immersion conjecture[J]. Journal of Combinatorial Theory, Series B, 2010,100 : 181-205.

二级参考文献83

  • 1Robertson N, Seymour P D. Graph Minors -- A Survey. In Surveys in Combinatorics 1985, Anderson I (ed.), Cambridge Univ. Press, Cambridge, 1985, pp.153-171.
  • 2Robertson N, Seymour P D. Graph minors VIII. A Kuratowski theorem for general surfaces. J. Combin. Theory Ser. B, 1990,48: 255-288.
  • 3Robertson N, Seymour P D. Graph minors XIII. The disjoint paths problem. J. Combin. Theory Ser. B, 1995, 63: 65-110.
  • 4Fellows M, Langston M. Nonconstructive tools for proving polynomial-time decidability. J. ACM, 1988, 35: 727-739.
  • 5DIMACS Workshop on Faster Exact Solutions for NP-Hard Problems. Princeton, Feb. 23-24, 2000.
  • 6Papadimitriou C H, Yannakakis M. Optimization, approximation, and complexity classes. Journal of Computer and System Sciences, 1991, 43: 425--440.
  • 7Impagliazzo R, Paturi R. Which problems have strongly exponential complexity? Journal of Computer and System Sciences, 2001, 63: 512-530.
  • 8Chen J, Chor B, Fellows M, Huang X, Juedes D, Kanj I, Xia G.Tight lower bounds for certain parameterized NP-hard problems. In Proc. 19th Annual IEEE Conference on Computational Complexity ( CCC 2004), 2004, pp.150-160.
  • 9Anthony M, Biggs N. Computational Learning Theory. Cambridge University Press, Cambridge, UK, 1992.
  • 10Papadimitriou C H, Yannakakis M. On limited nondeterminism and the complexity of VC dimension. Journal of Computer and System Sciences, 1996, 53: 161-170.

共引文献21

同被引文献41

  • 1Jian-ErChen.Parameterized Computation and Complexity： A New Approach Dealing with NP-Hardness[J].Journal of Computer Science & Technology,2005,20(1):18-37. 被引量：22
  • 2钟波,谢挺.关于正则图的路分解[J].西华大学学报（自然科学版）,2005,24(4):5-7. 被引量：3
  • 3汪小帆,李翔,陈关荣.2012网络科学导论(北京:高等教育出版社),第161页.
  • 4Nadja Betzler,Jiong Guo,Rolf Niedermeier.Parameterized computational complexity of Dodgson and Young elections[J].Information and Computation.2009(2)
  • 5Frank Dehne,Michael Fellows,Michael Langston,Frances Rosamond,Kim Stevens.An O(2O(k)n3) FPT Algorithm for the Undirected Feedback Vertex Set Problem[J].Theory of Computing Systems.2007(3)
  • 6Elena Prieto,Christian Sloper.Looking at the stars[J].Theoretical Computer Science.2005(3)
  • 7Jianer Chen,Donald K. Firesen,Weijia Jia,Iyad A. Kanj.Using Nondeterminism to Design Efficient Deterministic Algorithms[J].Algorithmica.2004(2)
  • 8Bruce Reed,Kaleigh Smith,Adrian Vetta.Finding odd cycle transversals[J].Operations Research Letters.2003(4)
  • 9Georg Gottlob,Francesco Scarcello,Martha Sideri.Fixed-parameter complexity in AI and nonmonotonic reasoning[J].Artificial Intelligence.2002(1)
  • 10Jianer Chen,Iyad A. Kanj,Weijia Jia.Vertex Cover: Further Observations and Further Improvements[J].Journal of Algorithms.2001(2)

引证文献5

二级引证文献7

计算机科学
2012年 第3期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部