Efficiently parallelizable problems on a class of decomposable graphs

作     者：Hsieh, SY 

作者机构：Natl Cheng Kung Univ Dept Comp Sci & Informat Engn Tainan 701 Taiwan 

出 版 物：《JOURNAL OF COMPUTER AND SYSTEM SCIENCES》 (计算机与系统科学杂志)

年 卷 期：2005年第70卷第1期

页      面：140-156页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：decomposable graphs parallel algorithms PRAM subgraph optimization problems rooted trees series-parallel graphs 

摘      要：In the literature, there are quite a few sequential and parallel algorithms to solve problems on decomposable graphs utilizing distinct techniques. Trees, series-parallel graphs, outerplanar graphs, and bandwidth-k graphs all belong to decomposable graphs. Let T-d (\V\, \E\) and P-d (\V\, \E\) denote the time complexity and processor complexity required to construct a parse tree representation T-G for a decomposable graph G = (V, E) on a PRAM model M-d. We define a general problem-solving paradigm to solve a wide class of subgraph optimization problems on decomposable graphs in O(T-d(\V\, \E\) +log \V(T-G)\) time using O(P-d(\V\, \E\) + (\V( TG)\)/(log \V\(TG)\)) processors on M-d. We also demonstrate the following examples fitting into our paradigm: (1) The maximum independent set problem on trees, (2) The maximum matching problem on series-parallel graphs, and (3) The efficient domination problem on series-parallel graphs. Our results improve the previously best known results of (1) and (2). (C) 2004 Elsevier Inc. All rights reserved.