旋轉圖(rotator graph)及三價凱利圖(trivalent Cayley graph)同屬於凱利圖(Cayley graphs)家族的成員。本論文探討在旋轉圖與不完全旋轉圖(incomplete rotator graphs)的最小回饋點/邊集合(feedback vertex/arc set)問題；以及在三價凱利圖上建構獨立展開樹的方法。
一個圖的回饋點/邊集合(簡稱FVS/FAS)是此圖的點/邊子集合，而此圖的每一個環路(cycle)至少有一個點/邊是在此子集合內，將此FVS/FAS從圖移除後，此圖剩下的部份將不存在任何的環路，而最小FVS/FAS是指包含最少點/邊的FVS/FAS。Hsu和Lin [22]在n!節點的旋轉圖上，提出一個時間複雜度為O(nn-3) 的建構FVS演算法：另外，他們證明此FVS的大小為n!/3而且是最小的。本論文提出一個有效率的演算法，此演算法同樣能在n!節點的旋轉圖上建構出大小為n!/3的FVS，而時間複雜度則只有O(n!)。換言之，我們可以旋轉圖節點數的線性時間複雜度(linear time complexity)之演算法得到最佳解。另外我們提出一個建構旋轉圖FAS的精簡集合式，並證明此集合式建構出的FAS是最小的，而此集合式很容易撰寫成一個有效率的演算法。最後，我們也在不完全旋轉圖上，提出一個建構最小FAS的集合式。
而建立多顆獨立擴展樹(independent spanning trees)在網路通訊方面有很多的應用，如容錯廣播(fault-tolerant broadcasting)和安全訊息發送(secure message distribution)。Cheriyan和Maheshwari [8] 證明所有3-連結的圖一定可以在O(|V||E|)的時間複雜度，建構出3顆獨立擴展樹。三價凱利圖是由Vadapalli and Srimani 在 [38] 所提出的節點分支度為3的互連網路(interconnection network)。本論文提出一個以三價凱利圖的任一節點當作樹根(root)建構3顆獨立擴展樹的線性時間演算法，而此演算法植基於一組描述每個節點的父節點的簡潔規則，因此使得這個演算法也很容易平行化。

Rotator graph and trivalent Cayley graph are two members of Cayley graphs. This dissertation studies the minimum feedback vertex/arc set in rotator and incomplete rotator graphs, as well as the independent spanning trees of trivalent Cayley graphs.
A feedback vertex/arc set (abbreviated as FVS/FAS) of a graph is a subset of the vertices/arcs which contains at least one vertex/arc for every cycle of the graph. Removing the FVS/FAS from the graph makes the remaining graph acyclic. A minimum FVS/FAS is an FVS/FAS which contains the smallest number of vertices/arcs. For a rotator graph with M = n! nodes, Hsu and Lin [22] first proposed an algorithm which constructed an FVS with time complexity O(nn-3). In addition, they found that the size of the FVS is M /3, which was proved to be minimum. In this dissertation, we present an efficient algorithm which constructs an FVS for a rotator graph in O(M) time and also obtains the minimum FVS size M /3. In other words, this algorithm derives the optimal result with the time complexity which is linearly proportional to the number of nodes in the rotator graph. In addition, we present a concise formula for finding an FAS for a rotator graph and prove that the FAS is minimum. This formula can be easily implemented by an efficient algorithm which obtains a minimum FAS in a rotator graph. Finally, we also present a concise formula for finding a minimum FAS in an incomplete rotator graph in this dissertation.
The construction of multiple independent spanning trees has many applications in network communication, such as fault-tolerant broadcasting and secure message distribution. Cheriyan and Maheshwari [8] showed that three independent spanning trees can be constructed in O(|V||E|) time for every 3-connected graph. In this dissertation, we present a linear time algorithm to construct three independent spanning trees rooted at any node in a trivalent Cayley graph, which was proposed by Vadapalli and Srimani in [38] for designing the topology of an interconnection network with constant regularity of node degree 3. In particular, our algorithm relies on a set of concise rules that describe the parent of nodes in each tree. Therefore, the construction scheme can be easily parallelized.

[1]V. Bafna, P. Berman, and T. Fujito, “A 2-approximation algorithm for the undirected feedback vertex set problem”, SIAM Journal on Discrete Mathmatics, vol. 12, no. 3, pp. 289-297 (1999).
[2]F. Bao, Y. Funyu, Y. Hamada, and Y. Igarashi, “Reliable broadcasting and secure distributing in channel networks”, Proceedings of 3rd International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN'97), Taipei, , pp. 472-478 (1997).
[3]R. Bar-Yehuda, D. Geiger, J. S. Naor, and 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).
[4]T. Calamoneri and R. Petreschi, “A new 3D representation of trivalent Cayley networks”, Information Processing Letters, vol. 61, no. 5, pp. 247-252 (1997).
[5]T. Calamoneri and R. Petreschi, “Optimal layout of trivalent Cayley interconnection networks”, International Journal of Foundations of Computer Science, vol. 10, no. 3, pp. 277-287 (1999).
[6]I. Caragiannis, C. Kaklamanis, and 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).
[7]P. Charbit, S. Thomasse, and A. Yeo, “The minimum feedback arc set problem is NP-hard for tournaments”, Combinatorics, Probability and Computing, vol. 16, no. 1, pp.1-4 (2007).
[8]J. Cheriyan and S. N. Maheshwari, “Finding nonseparating induced cycles and independent spanning trees in 3-connected graphs”, Journal of Algorithms, vol. 9, no. 4, pp. 507-537 (1988).
[9]P. F. Corbett, “Rotator graphs: an efficient topology for point-to-point multiprocessor networks”, IEEE Transactions on Parallel and Distributed Systems, vol. 3, no. 5, pp. 622-626 (1992).
[10]S. Curran, O. Lee, and X. Yu, “Finding four independent trees”, SIAM Journal on Computing, vol. 35, no. 5, pp. 1023-1058 (2006).
[11]P. Eades, X. Lin, and W. F. Smyth, “A fast and effective heuristic for the feedback arc set problem”, Information Processing Letters, vol. 47, no. 6, pp. 319-323 (1993).
[12]G. Even, S. Naor, B. Schieber, and M. Sudan, “Approximating minimum feedback sets and multicuts in directed graphs”, Algorithmica, vol. 20, no. 2, pp. 151-174 (1998).
[13]P. Festa, P. M. Pardalos, and M. G. C. Resende, “Feedback set problems”, Handbook of Combinatorial Optimization, Supplement volume A, Kluwer Academic Publishers, Boston, MA, pp. 209-258 (1999).
[14]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, no. 1, pp. 1-23 (1990).
[15]R. Focardi, F. L. Luccio, and D. Peleg, “Feedback vertex set in hypercubes”, Information Processing Letters, vol. 76, no. 1-2, pp. 1–5 (2000).
[16]M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco, CA (1979).
[17]Z. Ge and S. L. Hakimi, “Disjoint rooted spanning trees with small depths in deBruijn and Kautz graphs”, SIAM Journal on Computing, vol. 26, no. 1, pp. 79-92 (1997).
[18]J. Guo, F. Hüffner, and H. Moser, “Feedback arc set in bipartite tournament is NP-complete”, Information Processing Letters, vol. 102, no. 2-3, pp. 62-65 (2007).
[19]S. Gupta, “Feedback arc set problem in bipartite tournaments”, Information Processing Letters, vol. 105, no. 4, pp. 150-154 (2008).
[20]D. Gusfield, “A graph theoretic approach to statistical data security”, SIAM Journal on Computing, vol. 17, no. 3, pp. 552-571 (1998).
[21]T. Hasunuma and H. Nagamochi, “Independent spanning trees with small depths in iterated line digraphs”, Discrete Applied Mathematics, vol. 110, no. 2-3, pp. 189-211 (2001).
[22]C. C. Hsu, H. R. Lin, H. C. Chang, and K. K. Lin, “Feedback Vertex Sets in Rotator Graphs”, Lecture Notes in Computer Science, vol. 3984, pp.158-164 (2006).
[23]A. Itai and M. Rodeh, “The multi-tree approach to reliability in distributed networks”, Information and Computation, vol. 79, no. 1, pp. 43-59 (1988).
[24]Y. Iwasaki, Y. Kajiwara, K. Obokata, and Y. Igarashi, “Independent spanning trees of chordal rings”, Information Processing Letters, vol. 69, no. 3, pp. 155-160 (1999).
[25]D. S. Johnson, “Approximation algorithms for combinatorial problems”, Journal of Computer and System Sciences, vol. 9, no. 3, pp. 256-278 (1974).
[26]R. Kralovic and P. Ruzicka, “Minimum Feedback Vertex Sets in Shuffle-based Interconnection Networks”, Information Processing Letters, vol.86, no. 4, pp. 191–196 (2003).
[27]C. J. Kuo, C. C. Hsu, H. R. Lin, and K. K. Lin, “An Efficient Algorithm for Minimum Feedback Vertex Sets in Rotator Graphs”, Information Processing Letters, vol. 109, no. 9, pp. 450-453 (2009).
[28]F. L. Luccio, “Almost Exact Minimum Feedback Vertex Set in Meshes and Butterflies”, Information Processing Letters, vol. 66, no. 2, pp. 59–64 (1998).
[29]K. Obokata, Y. Iwasaki, F. Bao, and Y. Igarashi, “Independent spanning trees of product graphs and their construction”, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, vol. E79-A, no. 11, pp. 1894-1903 (1996).
[30]S. Okawa, “Correction to the diameter of trivalent Cayley graphs”, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, vol. E84-A, no. 5, pp. 1269-1272 (2001).
[31]S. Ponnuswamy and V. Chaudhary, “Embedding of cycles in rotator and incomplete rotator graphs”, Proceedings of the 6th IEEE Symposium on Parallel and Distributed Processing, pp. 603-610 (1994).
[32]V. Ramachandran, “Finding a minimum feedback arc set in reducible flow graphs”, Journal of Algorithms, vol. 9, no. 3, pp. 299-313 (1988).
[33]Y. Saab, “A fast and effective algorithm for the feedback arc set problem”, Journal of Heuristics, vol. 7, no. 3, pp. 235-250 (2001).
[34]A. Silberschatz, P. B. Galvin, and G. Gagne, Operating Systems Concepts, 6th edn, John Wiley and Sons, Inc., New York (2003).
[35]Y. Tanaka and Y. Shibata, “On the pagenumber of trivalent Cayley graphs”, Discrete Applied Mathematics, vol. 154, no. 8, pp. 1279-1292 (2006).
[36]Y. Tanaka and Y. Shibata, “A minimum feedback vertex in trivalent cayley graph”, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, vol. E89-A, no. 5, pp.1269-1274 (2006).
[37]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).
[38]P. Vadapalli and P. K. Srimani, “Trivalent Cayley graph for interconnection networks”, Information Processing Letters, vol. 54, no. 6, pp. 329-335 (1995).
[39]P. Vadapalli and P. K. Srimani, “Shortest routing in trivalent Cayley graph network”, Information Processing Letters, vol. 57, no. 4, pp. 183-188 (1996).
[40]M. D. Wagh and J. Mo, “Hamilton cycles in trivalent Cayley graphs”, Information Processing Letters, vol. 60, no. 4, pp. 177-181 (1996).
[41]F. H. Wang, C. J. Hsu, and J. C. Tsai, “Minimal feedback vertex sets in directed split-stars”, Networks, vol. 45, no. 4, pp. 218-223 (2005).
[42]F. H. Wang, Y. L. Wang, and J. M. Chang, “Feedback vertex sets in star graphs”, Information Processing Letters, vol. 89, no. 4, pp.203-208 (2004).
[43]J. S. Yang, J. M. Chang, S. M. Tang, and Y. L. Wang, “Reducing the height of independent spanning trees in chordal rings”, IEEE Transactions on Parallel and Distributed Systems, vol. 18, no. 5, pp. 644-657 (2007).
[44]J. S. Yang, S. M. Tang, J. M. Chang, and Y. L. Wang, “Parallel construction of optimal independent spanning trees on hypercubes”, Parallel Computing, vol. 33, no. 1, pp. 73-79 (2007).
[45]A. Zehavi and A. Itai, “Three tree-paths”, Journal of Graph Theory, vol. 13, no. 2, pp. 175-188 (1989).