# 臺灣博碩士論文加值系統

(3.236.225.157) 您好！臺灣時間：2022/08/16 00:38

:::

### 詳目顯示

:

• 被引用:0
• 點閱:242
• 評分:
• 下載:21
• 書目收藏:0
 摘要 所謂feedback vertex set即是將網路拓樸上的每個點都視為一個處理器，假設在拓樸上找出數個點，而且將這數個點刪除，使整個網路拓樸找不到環路，以消弭網路作業系統中的死結，則這些點所構成的點集合叫做 feedback vertex set 。在本論文中，我們探討有向及無向之split-stars與alternating group graphs在其網路拓樸架構裡，尋求最小feedback vertex set的問題，並且分別針對有向及無向的spilt-stars 與 alternating group graphs，利用不同的技巧，個別去求以上圖形的feedback vertex set大小之上、下限值。
 Abstract The feedback vertex set F of a graph G is a subset of vertices such that the removal of F from G induces an acyclic subgraph. In this paper, we study the feedback vertex set problem on the directed and undirected spilt-stars and alternating group graphs separately. We give upper and lower bounds to the minimum feedback vertex set on the n-dimensional spilt-stars and n-dimensional alternating group graphs.
 目錄 中文摘要 Ⅰ 英文摘要 Ⅱ 目錄 Ⅲ 圖目錄 Ⅳ 1. Introduction 1 2. The Feedback Vertex Set of Directed Spilt-stars 6 3. The Feedback Vertex Set of Directed Alternating Group Graphs 9 4. The Feedback Vertex Set of Undirected Spilt-stars 13 5. The Feedback Vertex Set of Undirected Alternating Group Graphs 21 6. Concluding Remarks 25 7. Reference 27
 [1]Eddie Cheng and Marc J. Lipman, Orienting spilt-stars and alternating group graphs, Networks, Vol. 35, pp. 139-144, 200.[2]E. Cheng, M. J Lipman, and H.A. Park, An attractive variation of the star graphs: spilt-stars, Technical Report No.98－3, Oakland University, 1998.[3]Riccardo Focardi and Flaminia L. Luccio, Minimum Feedback Vertex Set in K-Dimensional Hyercubes. Technical Report 26 October 1999.[4]M. R. Garey and D.S. Johnson. Computers and Intractability. Freeman, San Francisco 1979.[5]J. S. Jwo, S. Lakshmivarahan, and S.K. Dhall, A new class of interconnection networks based on the alternating group, Networks 23(1993), 315－326.[6]Y. D. Liang. On the feedback vertex set in permutation graphs. Information Processing Letters, 52, (3), 123－129, 1994.[7]Y. D. Liang and M. S. Cheng. Minimum Feedback Vertex Set in Cocomparability Graphs and Convex Bipartite Graphs. Acta Informatica, 34, 337－346, 1997.[8]E. L. Llyod and M. L. Soffa. On Locating Minimum Feedback Vertex Sets. Journal of Computer and System Sciences, 37, 292－311, 1988.[9]C. Lu and C. Tang. A linear-time algorithm for the weighted feedback vertex problem in interval graphs. Information Processing Letters, 61, (2), 107－112, 1997.[10]F. L. Luccio . Exact Minimum Feedback Vertex Set in Meshes and Butterflies. Information Processing Letters, 66, (2), 59－64, 1998.
 電子全文
 國圖紙本論文
 推文當script無法執行時可按︰推文 網路書籤當script無法執行時可按︰網路書籤 推薦當script無法執行時可按︰推薦 評分當script無法執行時可按︰評分 引用網址當script無法執行時可按︰引用網址 轉寄當script無法執行時可按︰轉寄

 無相關論文

 無相關期刊

 1 在樹及星狀網路上聯盟問題之研究 2 船舶電力系統小信號穩定度分析 3 船舶電力系統規劃與設計 4 動態邊界偵測在微陣列影像上的分析 5 MPEG-4自動調控播放之設計 6 針對多份xml文件之路徑查詢研究 7 三度空間與二次曲面之最短路徑規劃及動態追截 8 一種應用於車速自動偵測之適應性比對演算法 9 時戳服務模式與運作機制 10 快速預估方位演算法於三維空間寬頻訊號追蹤之應用 11 DS/CDMA編碼之分析與接收機之改善 12 電腦視覺與直流無刷馬達控制整合之桿上球系統研究 13 噴墨印表機列印系統之模式建立與參數判別 14 二維格狀運輸網路中具有轉彎加權之最佳路徑規劃 15 微波單石積體電路中平面式電感器與場效電晶體之製作

 簡易查詢 | 進階查詢 | 熱門排行 | 我的研究室