圖形上有關控制與邊置換成路徑的標號問題之研究

專案詳細資料

Description

延續之前計劃的主要成果,我們討論的問題是基於無線 傳輸的安全性及準確性的需求,必須考慮到的網路架構所形成 的圖形裡,每條邊必須加進兩個有方向性的傳輸中繼站,即每 條原架構底下的邊由一條長度為三的路徑所取代,然後在這樣 的圖形上探討L(2,1)標號的最佳值.原本被發表在國際期刊上 的已知結果僅限圖形的最大度數小於或等於2,其他都只是求 得上界而已.但我們在之前計劃支持下解決了所有最大度數大 於3 的圖形,等於3 就只知規律圖的最佳解(此結果即將發表於 Discrete Mathematics 338(2015) 248-255).因此我們除了想 完整解決度數為3 的情形, 更期望進一步討論每條邊由任意長 度的路徑取代的邊-路徑置換圖. 此外,我們也對此圖上類似 的L(p,q)標號問題感興趣. 我們也將考慮一些在圖形上控制問題的變形.原本的圖形 上的控制問題是找最少數目的點集合,使得圖上的任一點若不 在這個點集合裡,那與它相連接的點裡,至少有一點是落在這 個點集合裡.而我們考量的資源分配問題與控制問題相似,我 們希望找最少數目的點集合, 使得圖上的任一點若不在這個 點集合裡,那與它相連接的點裡,至少有二點其一是落在這個 點集合裡另一則不在這點集合裡.我們在類似的控制問題上已 有一些初步的結果,雖然這樣的問題就算只考慮二部圖也是已 被證明是NP-complete,也有人提出在樹圖上有linear time 的 演算法.我們期望能找出演算法有效解決一些特殊圖的最佳解. 另外延續之前計劃的工作, 繼續對有關的圖形標號加以研究.
狀態已完成
有效的開始/結束日期1/08/1531/07/16

指紋

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