專案詳細資料
Description
原本的圖形上的控制問題是找最少數目的點集合,使得圖上的任一點若不在這個點集合裡,那與它相連接的點裡,至少有一點是落在這個點集合裡.由於實際上的資源分享問題而考慮(t,r)擴散控制,1≦r≦t,希望找最少數目的點集合,集合裡的每個點給予完整的資源(用t 來衡量),這集合裡的點會供給與它距離為i 的點部分資源(用t-i 來衡量),所以與它最短距離≧t 的點就得不到它的資源,而圖上任一點都必須得到一定份量的資源供給(至少是r), 而目前僅有m x n 格子圖在t≦3, m≦5 有些確切值, 一般的格子圖也只t≦3 有上界.我已經能證明這樣的問題就算只考慮二部圖也是NP-complete.若是不限定集合的點給予資源皆相同, 只要求集合裡的所有點其資源總量要最少,則已知是polynomial time 就可解決的問題,一些特定的圖上還可以找到linear time 的演算法.所以希望再加入t 的限制後,一些規律的圖上能找到有效率的演算法來處理這樣的資源分配問題. 另外延續之前的工作, 繼續對有關的圖形標號相關問題加以研究.
狀態 | 已完成 |
---|---|
有效的開始/結束日期 | 1/08/17 → 31/07/18 |
指紋
探索此專案觸及的研究主題。這些標籤是根據基礎獎勵/補助款而產生。共同形成了獨特的指紋。