臺灣博碩士論文加值系統

摘要
所謂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.