Abstract
在這篇論文中，我們討論在常數個範圍之分散式無線電網路上的強連通問題。我們各用０（nm（１＋log n╱m ））和０（nlog n）的時間解決了一維和二維的連通性測定問題（Connectivity testing problem）。這裡n 為網路中轉發器（repeater）的個數，而m 為網路中轉發器所組成的群數。另外我們介紹了一些強連通網路的最佳建構以及重建構問題。也就是k 範圍指定問題（k-range assignment problem），最少k 範圍增加量問題（minimum k-range inc-rement problem），與更動最少個k 範圍轉發器問題（minimum number of k-rangeupdating problem ）。這些問題都是NP困難的。即使只有二種範圍規格也一樣。這裡用了廣為人知的問題化約性來證明。對於k 範圍指定問題，我們使用由Megiddo和Supowit 所提的技巧。這個技巧告訴我們如何把３滿足性問題（３－satisfiabil-ity problem ）化約成一般的幾何問題。最近這個技巧也被黃能富先生用來證明圓連通問題（Circle connecting problem ）的困難度。我們用了這個技巧建立一個從３滿足性問題到２範圍指定問題的化約（reduction ）。對於最少k 範圍增加量問題，我們建立一個從２範圍指定問題到最少２範增加量問題的化約。對於更動最少個k 範圍轉發器問題，我們建立一個從最少２範圍增加量問題到更動最少個２範圍轉發器問題的化約。由於３滿足問題是NP完全的（NP-complete ）。所以在只有兩個範圍規格下的這些問題都是NP困難的。很明顯地，只有兩個範圍規格下的這些問題都可化約為k 個範圍規格下的這些問題。所以我們可以得知這些問題都是NP困難的。