首页 | 本学科首页   官方微博 | 高级检索  
     检索      

图的树宽的结构性结果
引用本文:林诒勋.图的树宽的结构性结果[J].数学进展,2004,33(1):75-86.
作者姓名:林诒勋
作者单位:郑州大学数学系,郑州,河南,450052
基金项目:Project supported by NSFC(No.10071076).
摘    要:图G的树宽是使得G成为一个k-树的子图的最小整数k.树宽的算法性结果在图子式理论及有关领域中已有深入的研究.本文着重讨论其结构性结果,包括拓扑不变性、子式单调性、可分解性、刻画问题、与其它参数的关系及由此引伸出的性质.

关 键 词:图论  树宽  图子式  拓扑不变性  子式单调性  可分解性

Structural Aspects on the Treewidth of Graphs
LIN Yi-xun.Structural Aspects on the Treewidth of Graphs[J].Advances in Mathematics,2004,33(1):75-86.
Authors:LIN Yi-xun
Abstract:The treewidth of a graph G is the minimum integer k such that G is a subgraph of a k-tree. The algorithmic aspects of this notion have been well studied in graph minor theory and related areas. This paper is concerned with the structural aspects of treewidth, including the topological invariance, the minor monotonicity, the decomposability, relations with other parameters, and related results.
Keywords:graph-theoretic parameter  treewidth  graph minor  structural property
本文献已被 CNKI 维普 万方数据 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号