Spelling suggestions: "subject:"graph theory."" "subject:"raph theory.""
1 |
On 1-factorizations of the complete graph and the relationship to round robin schedulesGelling, Eric Neil 10 June 2016 (has links)
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
|
2 |
Closure operations and Hamiltonian properties of independent and total domination critical graphsSimmons, Jill. 10 April 2008 (has links)
No description available.
|
3 |
Graph expansions and applications.January 2015 (has links)
我們研究與圖的擴張值相關的問題。圖的擴張值反映了一個圖的連通程度。很多不同的應用問題都可以轉換成在圖中找一個不擴張的點集,而這亦跟近似理論中的唯一遊戲猜想(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.
|
4 |
Problems in graph connectivity /Gubbala, Prabhakar. January 2006 (has links)
Thesis (Ph. D.)--University of Texas at Dallas, 2006. / Includes vita. Includes bibliographical references (leaves 127-129).
|
5 |
Small cycle cover, group coloring with related problemsLi, Xiangwen, January 1900 (has links)
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).
|
6 |
Graph minorNiu, Jianbing. January 1900 (has links)
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).
|
7 |
Dynamic coloring of graphsMontgomery, Bruce Lee. January 2001 (has links)
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).
|
8 |
Chords of longest circuits of graphsLi, Xuechao. January 2001 (has links)
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).
|
9 |
Some results in graph theoryLaw, Ka-ho., 羅家豪. January 2010 (has links)
published_or_final_version / Mathematics / Doctoral / Doctor of Philosophy
|
10 |
Graph partitions and integer flowsChen, Xujin., 陳旭瑾. January 2004 (has links)
published_or_final_version / abstract / toc / Mathematics / Doctoral / Doctor of Philosophy
|
Page generated in 0.5241 seconds