1. You are Here：

作者: 資訊科學與工程研究所
關鍵字: 串并聯網路;參數值;不變量;周長;邊的連結性;顏色多項式;SIMD電腦;CREW-PRAW電腦;(INVARIANT);(GIRTH);(EDGE-CONNECTIVITY);(CHROM-ATIC-POLYNOMIAL);(THE-SHORTEST-COMPLETE-TOUR-PR
公開日期: 1990
摘要: 串并聯網路通常被用來當作電子線路之模型，通常串并聯網路以串并聯圖形來表示。 然而，對於每個串并聯網路通常存在許多不同的串并聯圖形表示法。對任何一個串并 聯網路其所有的串并聯圖形表示法之參數值，若都相同，稱此圖形的參數值為不變量 (lnvariant)。 本論文證明一些圖形的參數值為不變量，如周長(girth) 、邊的連結性(edge connec tivity)和顏色多項式(chrom atic polynomial)等等。也將證明在傳統SIMD電腦下， 這些參數值( 如周長和邊的邊結性) 能於線性時間求得；或在CREW PRAW 電腦下，用 n/logn處理機於O(logn) 時間求得。顏色多項式能在傳統SIMD電腦下, 於O(n ) 線性 時間求得：或在CREW PRAW 電腦下, 用n/logn處理機於O(nlog n) 時間求得。 最後，探討在串并聯圖形中最短完全旅行問題(the shortest complete tour proble m)中最重要的邊，串并聯圖形中最重要的邊就是少掉此邊比少掉其他的邊所花的成本 高，并且提出一線性時間的演算法來求此最重要的邊。
URI: http://140.113.39.130/cdrfb3/record/nctu/#NT792394025
http://hdl.handle.net/11536/55269
Appears in Collections:Thesis


Related Contents
Loading...