Author: |
郭啟容 Chi-Jung Kuo |
---|---|

Thesis Title: |
凱利圖上回饋問題及獨立擴展樹之研究 On the Study of Feedback Problems and Independent Spanning Trees in Cayley Graphs |

Advisor: |
徐俊傑
Chiun-Chieh Hsu |

Committee: |
王有禮
Yue-Li Wang 賴源正 Yuan-Cheng Lai 蕭培墉 Pei-Yung Hsiao 陳永昇 Yong-Sheng Chen |

Degree: |
博士 Doctor |

Department: |
管理學院 - 資訊管理系 Department of Information Management |

Thesis Publication Year: | 2010 |

Graduation Academic Year: | 98 |

Language: | 英文 |

Pages: | 68 |

Keywords (in Chinese): | 安全訊息發送 、容錯廣播 、獨立擴展樹 、三價凱利圖 、有向圖 、不完全旋轉圖 、旋轉圖 、回饋邊集合 、回饋點集合 |

Keywords (in other languages): | secure message distribution., fault-tolerant broadcasting, independent spanning tree, trivalent Cayley graph, directed cycle, incomplete rotator graph, rotator graph, feedback arc set, feedback vertex set |

Reference times: | Clicks: 169 Downloads: 0 |

Share: |

School Collection Retrieve National Library Collection Retrieve Error Report |

旋轉圖(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.

中文摘要 i
ABSTRACT iii
誌 謝 v
TABLE OF CONTENTS vi
LIST OF FIGURES viii
LIST OF TABLES ix
Chapter 1 Introduction 1
1.1 Feedback Vertex/Arc Set Problem 1
1.2 Independent Spanning Trees Problem 5
1.3 Outline of the Dissertation 8
Chapter 2 An Efficient Algorithm for Minimum Feedback Vertex Sets in Rotator Graphs 9
2.1 Preliminaries 9
2.2 The Algorithm for Minimum FVS in Rotator Graphs 13
Chapter 3 Minimum Feedback Arc Sets in Rotator and Incomplete Rotator Graphs 18
3.1 Preliminaries 18
3.2 A minimum FAS in Rotator Graphs 20
3.3 A minimum FAS in Incomplete Rotator Graphs 23
Chapter 4 Independent Spanning Trees on Trivalent Cayley Graphs 29
4.1 Trivalent Cayley Graphs and Their Cycle Structure 29
4.2 Construction of ISTs 37
4.3 Correctness 47
Chapter 5 Conclusion 62
REFERENCES 63

[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).

Full text public date This full text is not authorized to be published. (Internet public)

Full text public date This full text is not authorized to be published. (National library)

- On the Oriented Chromatic Number of Honeycomb Rectangular Tori
- Chinese Operational Flow Aided-design System
- On the Study of Feedback Problem in Cayley Graphs
- Fault-Tolerant Broadcasting Algorithm for Wormhole-Routed 2D Torus Networks
- Some Optimization Problems on Competition Graphs, Common Arcs of Cycles, and Property Matching