咨询与建议

看过本文的还看了

相关文献

该作者的其他文献

文献详情 >A linear-time ie algorithm for... 收藏

A linear-time ie algorithm for finding three-decompositions of small treewidth

为发现小 Treewidth ^ 的树分解的一个线性时间的算法*

作     者:Bodlaender, HL 

作者机构:Department of Computer Science Utrecht University 3508 TB Utrecht P. O. Box 80.089 Netherlands 

出 版 物:《SIAM JOURNAL ON COMPUTING》 (工业与应用数学会计算杂志)

年 卷 期:1996年第25卷第6期

页      面:1305-1317页

核心收录:

学科分类:07[理学] 070104[理学-应用数学] 0701[理学-数学] 0812[工学-计算机科学与技术(可授工学、理学学位)] 

主  题:graph algorithms treewidth pathwidth partial k-trees graph minors 

摘      要:In this paper, we give for constant k a linear-time algorithm that, given a graph G = (V, E), determines whether the treewidth of G is at most k and, if so, finds a tree-decomposition of G with treewidth at most k. A consequence is that every minor-closed class of graphs that does not contain all planar graphs has a linear-time recognition algorithm. Another consequence is that a similar result holds when we look instead for path-decompositions with pathwidth at mast some constant k.

读者评论 与其他读者分享你的观点

用户名:未登录
我的评分