咨询与建议

看过本文的还看了

相关文献

该作者的其他文献

文献详情 >DETERMINISTIC DECOMPOSITION OF... 收藏

DETERMINISTIC DECOMPOSITION OF RECURSIVE GRAPH CLASSES

作     者:BORIE, RB PARKER, RG TOVEY, CA 

作者机构:GEORGIA INST TECHNOLSCH IND & SYST ENGNATLANTAGA 30332 

出 版 物:《SIAM JOURNAL ON DISCRETE MATHEMATICS》 (工业与应用数学会离散数学杂志)

年 卷 期:1991年第4卷第4期

页      面:481-501页

核心收录:

学科分类:07[理学] 0701[理学-数学] 070101[理学-基础数学] 

主  题:SERIES-PARALLEL GRAPH DECOMPOSITION RECURSIVE GRAPH CLASS DYNAMIC PROGRAMMING LINEAR-TIME ALGORITHM 

摘      要:The Popular class of series-parallel graphs can be built recursively from single edges by combining smaller components via connections only at a fixed pair of vertices called terminals. This recursive construction property with a limited number of terminals is essential to the linear time solution of problems on these graphs. A second useful property of these graphs is that decomposition is deterministic with respect to the series-parallel rules. This implies that the parse-tree of decomposition (which is required by the algorithms) can be determined in a straightforward manner by repeatedly applying the decomposition rules. Subject to retaining these properties, we examine how far the series-parallel graphs can be generalized. Corollaries of our results yield the deterministic decomposition of the series-parallel and Halin graph classes.

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

用户名:未登录
我的评分