Please wait a minute...
北京大学期刊网 | 作者  审稿人  编委专家  工作人员

首页   |   关于   |   浏览   |   投稿指南   |   新闻公告
数学进展
研究论文
图的树宽的结构性结果(英文)
Structural Aspects on the Treewidth of Graphs

林诒勋
LIN Yi-xun

郑州大学数学系 郑州,河南,450052
(Dept of Math., Zhengzhou Univ., Zhengzhou, Henan, 450052, P. R. China

收稿日期: 2004-02-25
出版日期: 2004-02-25

74
浏览

引用导出
0
    /   /   推荐

摘要 图G的树宽是使得G成为一个k-树的子图的最小整数k.树宽的算法性结果在图子式理论及有关领域中已有深入的研究.本文着重讨论其结构性结果,包括拓扑不变性、子式单调性、可分解性、刻画问题、与其它参数的关系及由此引伸出的性质.
关键词 图论参数树宽图子式结构性质    
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.
Key words treewidth    graph minor    structural property
[1] 潘文华, 徐常青. 无$K_4$-图子式的图的邻和可区别边染色[J]. 数学进展, 2017, 46(6): 839-847.
[2] 董广华,王宁,黄元秋,任韩,刘彦佩. 顶点劈分与图的上可嵌入性[J]. 数学进展, 2014, 43(5): 711-724.
Viewed
Full text


Abstract

Cited

首页 · 关于 · 关于OA · 法律公告 · 收录须知 · 联系我们 · 注册 · 登录


© 2015-2017 北京大学图书馆 .