The following new results concerning 1-factorizations of the complete graph are proved: (1) There are exactly 6 equivalence classes of 1-factorizations of the complete graph with 8 vertices. (2). There are exactly 396 equivalence classes of 1-factorizations of the complete graph with 10 vertices. Representatives of each of the equivalence classes are presented. The size of the automorphism group of each equivalence class of 1-factorizations of the complete graph with 2n vertices for n ≤ 5 is also found. Several theorems and results related to 1-factorizations of the complete graph are presented, and the relationship to round robin schedules is shown. An application problem demonstrates the importance of the choice of the equivalence class of round robin schedules in the solvability of the problem. / Graduate

No description available.

我們研究與圖的擴張值相關的問題。圖的擴張值反映了一個圖的連通程度。很多不同的應用問題都可以轉換成在圖中找一個不擴張的點集，而這亦跟近似理論中的唯一遊戲猜想(unique games conjecture) 有密切的關係。故此，圖的擴張值在應用和理論上均有研究動機。 / 我們介紹有關圖的擴張值的新發現。這些發現包括設計和分析找不擴張的子集的算法、近似算法的困難結論，以及擴張圖的算法應用： / 我們用更多的特徵值去證明一個Cheeger 不等式的推廣，從而較好地分析譜分割算法(spectral graph partitioning algorithm)。 / 我們分析圖上的隨機漫走來設計一個局部的圖分割算法。此算法跟Cheeger 不等式的保證相合。 / 我們給出圖冪的擴張值的緊下界，並用以得到一個關於找小的不擴張子集的困難結論(hardness result)。 / 我們利用擴張圖來設計一個快而簡單的算法來計算矩陣的秩，新算法顯著地改進了以往的算法。 / We study problems related to graph expansions, which measure how well a graph is connected. Various practical problems can be modelled as finding a small non-expanding subset of vertices, and this is also closely related to the unique games conjecture in the theory of approximation algorithms. Hence our study of graph expansions is both practically and theoretically motivated. / We present our new results about graph expansions. The results include the design and analysis of algorithms for finding non-expanding subsets, hardness of approximation results and algorithmic applications of expanders: / We prove a generalization of Cheeger's inequality using higher eigenvalues, providing a better analysis of the spectral graph partitioning algorithm. / We design a local graph partitioning algorithm using random walks on graph, matching the performance guaranteed by Cheeger's inequality. / We give a tight lower bound for the expansion of graph powers and use it to prove hardness results for small set expansions. / We use expanders to design fast and simple algorithms for computing matrix ranks, significantly improving over previous works. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Kwok, Tsz Chiu. / Thesis (Ph.D.) Chinese University of Hong Kong, 2015. / Includes bibliographical references (leaves 104-109). / Abstracts also in Chinese.

Thesis (Ph. D.)--University of Texas at Dallas, 2006. / Includes vita. Includes bibliographical references (leaves 127-129).

Thesis (Ph. D.)--West Virginia University, 2002. / Title from document title page. Document formatted into pages; contains vi, 120 p. : ill. Includes abstract. Includes bibliographical references (p. 114-120).

Thesis (Ph. D.)--West Virginia University, 2004. / Title from document title page. Document formatted into pages; contains vi, 55 p. Includes abstract. Includes bibliographical references (p. 53-55).

Thesis (Ph. D.)--West Virginia University, 2001. / Title from document title page. Document formatted into pages; contains viii, 52 p. : ill. Vita. Includes abstract. Includes bibliographical references (p. 51).

Thesis (Ph. D.)--West Virginia University, 2001. / Title from document title page. Document formatted into pages; contains vi, 57 p. : ill. Includes abstract. Includes bibliographical references (p. 56-57).

published_or_final_version / Mathematics / Doctoral / Doctor of Philosophy

published_or_final_version / abstract / toc / Mathematics / Doctoral / Doctor of Philosophy