跳到主要內容

臺灣博碩士論文加值系統

(3.236.225.157) 您好!臺灣時間:2022/08/16 00:38
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:許呈如
研究生(外文):Chen-Ju Hsu
論文名稱:在分割星狀網路與交替群圖上求回饋點集合與獨立點集合大小之上下限值
論文名稱(外文):The bounds of the feedback vertex set and independent set for the split-stars and alternating group graphs
指導教授:林英仁
指導教授(外文):In-Jen Lin
學位類別:碩士
校院名稱:國立海洋大學
系所名稱:資訊科學學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2002
畢業學年度:90
語文別:英文
論文頁數:28
中文關鍵詞:回饋點集合獨立點集合分割星狀網路交替群圖
外文關鍵詞:feedback vertex setindependent setsplit-starsalternating group graphs
相關次數:
  • 被引用被引用: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.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top