Parallel decomposition of generalized series-parallel graphs

NCUIR > College of Electrical Engineering & Computer Science > Graduate Institute of Computer Science and Information Engineering > journal & Dissertation > Item 987654321/29154

Please use this identifier to cite or link to this item: http://ir.lib.ncu.edu.tw/handle/987654321/29154

Title:	Parallel decomposition of generalized series-parallel graphs
Authors:	Ho,CW;Hsieh,SY;Chen,GH
Contributors:	資訊工程研究所
Keywords:	ALGORITHM
Date:	1999
Issue Date:	2010-06-29 20:15:00 (UTC+8)
Publisher:	中央大學
Abstract:	Generalized series-parallel (GSP) graphs belong to the class of decomposable graphs which can be represented by their decomposition trees. Given a decomposition tree of a GSP graph, there are many graph-theoretic problems which can be solved efficiently. An efficient parallel algorithm for constructing a decomposition tree of a given GSP graph is presented. It takes O(log n) time with C(m, n) processors on a CRCW PRAM, where C(m, n) is the number of processors required to find connected components of a graph with m edges and n vertices in logarithmic time. Based on our algorithmic results, we also derive some properties for GSP graphs, which may be of interest in and of themselves.
Relation:	JOURNAL OF INFORMATION SCIENCE AND ENGINEERING
Appears in Collections:	[Graduate Institute of Computer Science and Information Engineering] journal & Dissertation

Files in This Item:

File	Description	Size	Format
index.html		0Kb	HTML	460	View/Open

社群 sharing