資料載入中.....
|
請使用永久網址來引用或連結此文件:
http://ir.ncue.edu.tw/ir/handle/987654321/9977
|
| 題名: | Single step searching in weighted block graphs |
| 作者: | Hsiao, Ju-Yuan;Tang, C. Y.;Chang, R. S.;Lee, R. C. T. |
| 貢獻者: | 資訊工程系 |
| 日期: | 1994-11
|
| 上傳時間: | 2012-05-02T09:36:49Z
|
| 出版者: | Elsevier BV |
| 摘要: | In this paper, three types of problems for single step searching weighted graphs are investigated; the summation minimization (S-type, for short), bottleneck minimization (B-type, for short), and hybrid (H-type, for short) weighted single step graph searching problems. All three types are shown to be NP-hard but polynomial solvable for block graphs. The S-type problem is proved to be linearly equivalent to the optimum weight 2-independent set problem. Then we solve the S-type problem on a block graph G in linear time by solving the optimum weight 2-independent set problem on G. To solve the B-type problem, the first phase computes the bottleneck cost and the second phase constructs the searching plan by applying the S-type algorithm using the bottleneck cost derived in the first phase. Finally, an time algorithm for solving the H-type problem on weighted block graphs is proposed. |
| 關聯: | Information Sciences, 81(1-2): 1-29 |
| 顯示於類別: | [資訊工程學系] 期刊論文
|
文件中的檔案:
| 檔案 |
大小 | 格式 | 瀏覽次數 |
|---|
| 2050400410002.pdf | 8Kb | Adobe PDF | 496 | 檢視/開啟 |
|
在NCUEIR中所有的資料項目都受到原著作權保護.
|
