版权所有:内蒙古大学图书馆 技术提供:维普资讯• 智图
内蒙古自治区呼和浩特市赛罕区大学西街235号 邮编: 010021
作者机构: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.