設計與探討圖形上有(t,r)關擴散控制的演算法(2/2)

專案詳細資料

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/1831/07/19

指紋

探索此專案觸及的研究主題。這些標籤是根據基礎獎勵/補助款而產生。共同形成了獨特的指紋。