東華大學圖書館 |

語系: 繁體中文

說明(常見問題)

回圖書館首頁

手機版館藏查詢

登入

回首頁

切換: 標籤 | MARC模式 | ISBD

Competitive versions of vertex ranki...

McDonald, Daniel Cooper.

FindBook

Google Book

Amazon

博客來

Competitive versions of vertex ranking and game acquisition, and a problem on proper colorings.

紀錄類型:	書目-電子資源 : Monograph/item
正題名/作者:	Competitive versions of vertex ranking and game acquisition, and a problem on proper colorings./
作者:	McDonald, Daniel Cooper.
出版者:	Ann Arbor : ProQuest Dissertations & Theses, : 2015,
面頁冊數:	105 p.
附註:	Source: Dissertation Abstracts International, Volume: 77-05(E), Section: B.
Contained By:	Dissertation Abstracts International77-05B(E).
標題:	Mathematics. -
電子資源:	http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=3740512
ISBN:	9781339326290

Competitive versions of vertex ranking and game acquisition, and a problem on proper colorings.
McDonald, Daniel Cooper.

Competitive versions of vertex ranking and game acquisition, and a problem on proper colorings. - Ann Arbor : ProQuest Dissertations & Theses, 2015 - 105 p.

Source: Dissertation Abstracts International, Volume: 77-05(E), Section: B.

Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 2015.

In this thesis we study certain functions on graphs. Chapters 2 and 3 deal with variations on vertex ranking, a type of node-labeling scheme that models a parallel processing problem. A k-ranking of a graph G is a labeling of its vertices from {1,..., k} such that any nontrivial path whose endpoints have the same label contains a vertex with a larger label. In Chapter 2, we investigate the problem of list ranking, wherein every vertex of G is assigned a set of possible labels, and a ranking must be constructed by labeling each vertex from its list; the list ranking number of G is the minimum k such that if every vertex is assigned a set of k possible labels, then G is guaranteed to have a ranking from these lists. We compute the list ranking numbers of paths, cycles, and trees with many leaves. In Chapter 3, we investigate the problem of on-line ranking, which asks for an algorithm to rank the vertices of G as they are revealed one at a time in the subgraph of G induced by the vertices revealed so far. The on-line ranking number of G is the minimum over all such labeling algorithms of the largest label that the algorithm can be forced to use. We give algorithmic bounds on the on-line ranking number of trees in terms of maximum degree, diameter, and number of internal vertices.

ISBN: 9781339326290Subjects--Topical Terms:

515831
Mathematics.

Competitive versions of vertex ranking and game acquisition, and a problem on proper colorings.
LDR:03316nmm a2200313 4500 001 2117768
005 20170530090544.5
008 180830s2015 ||||||||||||||||| ||eng d
020 $a 9781339326290
035 $a (MiAaPQ)AAI3740512
035 $a AAI3740512
040 $a MiAaPQ $c MiAaPQ
100 1 $a McDonald, Daniel Cooper. $3 3279566
245 1 0 $a Competitive versions of vertex ranking and game acquisition, and a problem on proper colorings.
260 1 $a Ann Arbor : $b ProQuest Dissertations & Theses, $c 2015
300 $a 105 p.
500 $a Source: Dissertation Abstracts International, Volume: 77-05(E), Section: B.
500 $a Adviser: Bruce Reznick.
502 $a Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 2015.
520 $a In this thesis we study certain functions on graphs. Chapters 2 and 3 deal with variations on vertex ranking, a type of node-labeling scheme that models a parallel processing problem. A k-ranking of a graph G is a labeling of its vertices from {1,..., k} such that any nontrivial path whose endpoints have the same label contains a vertex with a larger label. In Chapter 2, we investigate the problem of list ranking, wherein every vertex of G is assigned a set of possible labels, and a ranking must be constructed by labeling each vertex from its list; the list ranking number of G is the minimum k such that if every vertex is assigned a set of k possible labels, then G is guaranteed to have a ranking from these lists. We compute the list ranking numbers of paths, cycles, and trees with many leaves. In Chapter 3, we investigate the problem of on-line ranking, which asks for an algorithm to rank the vertices of G as they are revealed one at a time in the subgraph of G induced by the vertices revealed so far. The on-line ranking number of G is the minimum over all such labeling algorithms of the largest label that the algorithm can be forced to use. We give algorithmic bounds on the on-line ranking number of trees in terms of maximum degree, diameter, and number of internal vertices.
520 $a Chapter 4 is concerned with the connectedness and Hamiltonicity of the graph G(j/k) ( H), whose vertices are the proper k-colorings of a given graph H, with edges joining colorings that differ only on a set of vertices contained within a connected subgraph of H on at most j vertices. We introduce and study the parameters gk(H) and hk(H), which denote the minimum j such that G(j/k) (H) is connected or Hamiltonian, respectively. Finally, in Chapter 5 we compute the game acquisition number of complete bipartite graphs. An acquisition move in a weighted graph G consists a vertex v taking all the weight from a neighbor whose weight is at most the weight of v. In the acquisition game on G, each vertex initially has weight 1, and players Min and Max alternate acquisition moves until the set of vertices remaining with positive weight is an independent set. Min seeks to minimize the size of the final independent set, while Max seeks to maximize it; the game acquisition number is the size of the final set under optimal play.
590 $a School code: 0090.
650 4 $a Mathematics. $3 515831
650 4 $a Theoretical mathematics. $3 3173530
650 4 $a Applied mathematics. $3 2122814
690 $a 0405
690 $a 0642
690 $a 0364
710 2 $a University of Illinois at Urbana-Champaign. $b Mathematics. $3 2099175
773 0 $t Dissertation Abstracts International $g 77-05B(E).
790 $a 0090
791 $a Ph.D.
792 $a 2015
793 $a English
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=3740512