設計有效率的平行演算法去辦識序列平行圖;Design Efficient Parallel Algorithms for Recognizing Series-Parallel Graphs

NCUIR > College of Electrical Engineering & Computer Science > Department of Computer Science and information Engineering > Research Project > Item 987654321/57119

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

Title:	設計有效率的平行演算法去辦識序列平行圖;Design Efficient Parallel Algorithms for Recognizing Series-Parallel Graphs
Authors:	何錦文
Contributors:	中央大學資訊工程學系
Keywords:	資訊工程--硬體工程;平行演算法;序列平行圖;平行隨機存取機器模式;開放式耳朵分解;分解樹;Parallel algorithm;Series-parallel graphs;Parallel random access machine;Open ear decomposition;Decomposition tree
Date:	1995-09-01
Issue Date:	2012-10-01 15:14:32 (UTC+8)
Publisher:	行政院國家科學委員會
Abstract:	本計畫是為期一年的計畫.在此計畫中,我們將研究如何在平行隨機存取機器模式下設計一個有效率的平行演算法來辨識序列平行圖( Series parallel graphs),並為序列平行圖建構一個分解樹(Decomposition tree).序列平行圖是一種可由單一邊開始,不斷地運用序列合成(Series composition) 和平行合成(Parallel composition)所產生的一種圖形.這種圖形在電子電路、排程問題和系統的可靠性等相關領域上提供了重要的應用.而分解樹可用來表示序列平行圖的結構,樹中的每個內點(Internal vertice)代表一種合成運算( Composition operator),而每個樹葉(Leaf)則代表序列平行圖的邊(Edge).假若給定一個序列平行圖的分解樹,那麼在序列平行圖所探討的一些最佳化子圖問題(Optimal subgraph problems)像最大獨立子集(Maximum independent set),最多配對(Maximum matching) 和最大終結子集(Maximum dominatingset)...等可在不可同時讀寫的平行隨機存取機器(EREW PRAM)下以最佳花費(Cost optimal)的演算法求解;也就是說這類問題可以在O(logn)的時間內用O(n/logn)個處理器來完成.由此可見有效率的建構出分解樹可直接改進上述問題的時間複雜度.而目前用來識別序列平行圖並建構出分解樹的演算法尚須使用O(n)個處理器在O(log/sup 2/n)時間內在EREW中完成.此處的n是輸入圖形的大小.所以,若我們能將辨識序列平行圖的演算法加以改進,那麼許多用來解決有關於序列平行圖的圖論問題的花費和時間都將大大的節省下來. ; 研究期間 8308 ~ 8407
Relation:	財團法人國家實驗研究院科技政策研究與資訊中心
Appears in Collections:	[Department of Computer Science and information Engineering] Research Project

Files in This Item:

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

社群 sharing

Loading...