專案詳細資料
Description
原本的圖形上的控制問題是找最少數目的點集合,使得圖上的任一點若不在這個點集合裡,那與它相連接的點裡,至少有一點是落在這個點集合裡.由於實際上的資源分享問題,最近有國外學者考慮(t,r)擴散控制,1≦r≦t,希望找最少數目的點集合,集合裡的每個點給予完整的資源(用t 來衡量),這集合裡的點會供給與它距離為i 的點部分資源(用t-i 來衡量),所以與它最短距離≧t 的點就得不到它的資源,而圖上任一點都必須得到一定份量的資源供給(至少是r), 而已知的成果非常少, 都是探討m x n 格子圖,且只有t≦3, m≦5 有些確切值, 一般的格子圖也只有 t≦3 有上界.事實上我在96 年的研究計劃裡考慮的控制問題就是這種問題在t=3,r=3 的情形.結合以往的研究成果,希望可以在這個課題上有不錯的成果,包括證明這樣的問題就算只考慮二部圖也是NP-complete. 另外延續之前計劃的工作, 繼續對有關的圖形標號加以研究.
| 狀態 | 已完成 |
|---|---|
| 有效的開始/結束日期 | 1/08/16 → 31/07/17 |
指紋
探索此專案觸及的研究主題。這些標籤是根據基礎獎勵/補助款而產生。共同形成了獨特的指紋。