本論文主要研究的問題是在連結網路(interconnection networks)上的回饋問題(feedback problems)。回饋問題分為兩類：針對點和邊分別稱為回饋點集合(feedback vertex set)及回饋邊集合(feedback arc set)。
　　圖G=(V,E)的一個回饋點集合F是圖G中點集合V的一個子集合，而且當F從G中被移除後，剩下的點所形成的圖形將不會有任何的環路(cycle)存在；同樣的，回饋邊集合H是圖G中邊集合E的一個子集合，而且當H從G中被移除後，剩下的邊所形成的圖形也將不會有任何的環路存在。
　　一般圖(general graphs)上，回饋點集合問題及回饋邊集合問題已被證明為NP-hard，但是針對特殊圖形上已提出許多多項式複雜度的演算法，在此論文中，我們將針對兩種凱利圖形(cayley graphs)：旋轉圖(rotator graphs)及三價凱利圖(trivalent cayley graphs)進行研究。旋轉圖是一種有方向性的排列圖(permutation graphs)，它和星狀圖(star graphs)及超立方體(hypercube)等凱利圖(cayley graphs)的家族圖形一樣，具有點對稱(node symmetric)及遞迴建構(recursive construction)等特性；並且在相同的節點數之下，旋轉圖甚至比星狀圖具有更好的特性，例如更小的直徑。三價凱利圖也同樣屬於凱利圖家族成員之一，擁有每個節點皆為分支度(degree)為3的良好特性，而不會隨著節點數的增加而改變，此種特性對於失敗節點的容忍度有很大的幫助。由於凱利圖在多處理器系統上能展現其優良的特性，因此，在這種架構下的回饋問題是有趣且值得研究的問題。

In this thesis, we address the feedback problems in interconnection networks. The feedback problem is divided into two kinds : feedback vertex set and feedback arc set.
A feedback vertex set of a graph G = (V, E) is a subset of vertices F V whose removal from G induces an acyclic graph G' = (V', E') with V' = VF and E' = {(u,v) E : u,v V'}. Similarly, a feedback arc set of a graph G is a subset of arcs H E whose removal from G induces an acyclic graph.
The problem of finding feedback vertex set and feedback arc set of a general graph has been proved to be NP-hard, although polynomial time solutions have been found for particular classes of graph. In this thesis, we study the feedback problem in two kinds of Cayley Graphs : Rotator Graph and Trivalent Cayley Graph. A Rotator Graph is a directed permutation graph and it is also a family of Cayley Graph, which has the characteristics of node symmetry and recursive construction just like those of star and pancake graphs. When the graphs have the same number of nodes, the Rotator Graph has better properties than those of star and pancake graphs, for example, the Rotator Graph has smaller diameter than that of Star Graph. The Trivalent Cayley Graph is also a family of Cayley Graphs. It is regular of degree 3 independent of the size of the graph. These characteristics are very helpful for fault tolerance. For these excellent properties of Cayley Graphs, it is interesting and worthy to discuss the feedback problems on this kind of networks.

[1]S.B. Akers and B. Krishnamurthy: A group theoretic model for symmetric interconnecton networks, IEEE Transaction on Computers, vol. 38, pp. 555-566, 1989.
[2]R. Bar-Yehuda, D. Geiger, J.S. Naor, R.M. Roth: Approximation algorithms for the feedback vertex set problem with applications to constraint satisfaction and Bayesian inference, SIAM Journal on Computing, vol. 27, no. 4, pp. 942-959, 1998.
[3]Peter F. Corbett, Rotator Graphs: An Efficient Topology for Point-to-Point Multiprocessor Networks, IEEE Transactions on Parallel and Distributed System, vol. 3, no. 5, pp. 622-626, September 1992.
[4]C. Chen, D.P. Agrawal and J.r. Burke, dBCube: A new class of hierarchical multiprocessor interconnection networks with area efficient layout, IEEE Trans. on Parallel and Distributed Systems, vol. 4, pp. 1332-1344, 1993.
[5]I. Caragiannis, C. Kaklamanis, P. Kanellopoulos: New bounds on the size of the feedback vertex set on meshes and butterflies, Information Processing Letters, vol. 83, no. 5, pp. 275-280, 2002.
[6]P. Erdos, and L. Posa: On the maximal number of disjoint circuits of a graph, Publicationes Mathematicae Debrecen, vol. 9, pp. 3-12, 1962.
[7]M.M. Flood: Exact and heuristic algorithms for the weighted feedback arc set problem: A special case of the skew-symmetric quadratic assignment problem, Networks, vol. 20, pp. 1-23, 1990.
[8]R. Floyd: Assigning Meaning to Programs, In Proceedings of Symposium on Applied Mathematics, vol. XIX, pp. 19-32, 1967.
[9]R. Focardi, F.L. Luccio, D. Peleg: Feedback vertex set in hypercubes, Information Processing Letters, vol. 76, no. 1-2, pp. 1-5, 2000.
[10]P. Festa, P.M. Pardalos, and M.G.C. Resende: Feedback Set Problems, In Handbook of Combinatorial Optimization, vol. 4, Kluwer Academic Publishers, 1999.
[11]D. Gusfield: A graph theoretic approach to statistical data security, SIAM Journal on Computing, vol. 17, no. 3, pp. 552-571, 1998.
[12]M.R. Garey, D.S. Johnson: Computers and Intractability, Freeman, San Francisco, CA, 1979.
[13]D.S. Johnson: Approximation algorithms for combinatorial problems, Journal of Computer and System Sciences 9 , pp. 256-278, 1974
[14]Z. Jovanovic, J. Misic: On fault tolerance of the star graph interconnection network, Information Processing Letters, vol. 49, no. 3, pp. 145-150, 1994.
[15]J. Kleinberg, A. Kumar: Wavelength conversion in optical networks, In Proceedings of the tenth annual ACM-SIAM symposium on Discrete Algorithms, pp. 566-575, 1999.
[16]R. Kralovic, P. Ruzicka: Minimum feedback vertex sets in shuffle-based interconnection networks, Information Processing Letters, vol. 86, no. 4, pp. 191-196, 2003.
[17]D. Kratsch, H. Muller, I. Todinca: Feedback vertex set and longest induced path on AT-free graphs, Graph-Theoretic Concepts in Computer Science - 29th International Workshop,WG 2003, pp. 309-321 Springer-Verlag, 2003.
[18]S. Latifi: On fault-diameter of the star graph, Information Processing Letters, vol. 46, pp. 142-150, 1993.
[19]S. Latifi: A routing and broadcasting scheme on faulty star graph, IEEE Trans. On Computers, vol. 42, no. 11, pp. 1398-1403, 1993.
[20]S. Latifi: Task allocation in the star graph, IEEE Trans. on Parallel and Distributed Systems, vol. 5, no. 11, November 1994.
[21]S. Latifi: Migration of tasks in interconnection network based on the star graph, Journal of Parallel and Distributed Computing, vol. 31, no. 2, pp. 166-173, December 1995.
[22]Y.D. Liang: On the feedback vertex set in permutation graphs, Information Processing Letters, vol. 52, no. 3, pp. 123-129, 1994.
[23]F.L. Luccio: Exact minimum feedback vertex set in meshes and butterflies, Information Processing Letters, vol. 66, no. 2, pp. 59-64, April 1998.
[24]Y.D. Liang, M.S. Soffa: On locating minimum feedback vertex sets, Journal of Computer and System Science, vol. 37, no. 3, pp. 292-311, December 1998.
[25]C. Lu, C. Tang: A linear-time algorithm for the weighted feedback vertex problem on interval graphs, Information Processing Letters, vol. 61, no. 2, pp. 107-112, 1997.
[26]B. Monien, and R. Schultz: Four approximation algorithms for the feedback vertex set problems, 7th Conference on Graph Theoretic Concepts of Computer Science, Hanser-Verlan, Munich, pp. 315-326, 1981.
[27]J. Misic, Z. Jovanovic: Routing function and deadlock avoidance in a star graph interconnection network, Journal of Parallel and Distributed Computing, vol. 22, pp. 216-228, 1994.
[28]D. Peleg: Local majority voting, small coalitions and controlling monopolies in graphs: A review, in: Proc. 3rd Colloquium on Structural Information and Communication Complexity, pp. 170-179, 1996.
[29]S. Ponnuswamy: Cayley graphs for point-to-point communication and VLSI implementation, TR-95-33 (draft).
[30]Y. Rouskov, S. Latifi, P.K. Srimani: Conditional fault diameter of star graph networks, Journal of Parallel and Distributed Computing, vol. 33, no. 1, pp.91-97, February 1996.
[31]Y. Rouskov, P.K. Srimani: Fault diameter of star graphs, Information Processing Letters, vol. 48, no. 5, pp. 243-251, 1993.
[32]A. Shamir, A linear time algorithm for finding minimum reducible graphs, SIAM Journal on Computing, vol. 8, no. 4, pp. 645-655, 1979.
[33]S. Sur, P.K. Srimani: Topological properties of star graphs, Computers and Mathematics Applications, vol. 25, pp. 87-98, 1993.
[34]G.W. Smith, R.B. Walford: The identification of a minimal feedback vertex set of a directed graph, IEEE Trans. On Circuits and Systems, vol. CAS-22, no. 1, pp. 9-14, 1975.
[35]O. Togni: Placement de convertisseurs de longueurs d’ondes dans les reseaux optiques, In Proceedings of ALGOTEL’00, 2000.
[36]C.H. Tsai, C.N. Hung, L.H. Hsu, and C.H. Chang: The correct diameter of trivalent Cayley graphs, Information Processing Letters, vol. 72, no. 3-4, pp. 109-111, 1999.
[37]P. Vadapalli and P.K. Srimani: Trivalent Cayley graphs for interconnection network, Information Processing Letters, vol. 54, no. 6, pp. 329-335,1995.
[38]C. Wang, E.L. Lloyd, M.L. Soffa: Feedback vertex sets and cyclically reducible graphs, Journal of the ACM, vol. 32, no. 2, pp. 296-313, 1985.
[39]M.D. Wagh, J. Mo: Hamilton cycles in Trivalent Cayley graphs, Information Processing Letters, vol. 60, no. 4, pp. 177-181, 1996.
[40]F.H. Wang, Y.L. Wang, J.M. Chang: Feedback vertex sets in star graphs, Information Processing Letters, vol. 89, no. 4, pp. 203-208, 2004.
[41]M. Yannakakis, Node-deletion problem on bipartite graphs, SIAM Journal on Computing, vol. 10, pp. 310-327, 1981.