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.