Thesis (Ph. D.)--University of Canterbury, 2008. / Typescript (photocopy). Includes bibliographical references (leaves 265-282). Also available via the World Wide Web.

Thesis (M.E.)--University of Canterbury, 2009. / Typescript (photocopy). Includes bibliographical references (leaves 139-142). Also available via the World Wide Web.

Thesis (Ph. D.)--University of Texas at Austin, 2003. / Vita. Includes bibliographical references. Available also from UMI Company.

Thesis (M.S.)--University of Michigan, 1980.

Thesis (M.Sc.)--Acadia University, 2006. / Includes bibliographical references (leaves 142-143). Also available on the Internet via the World Wide Web.

Thesis (Ph. D.)--University of Oregon, 1999. / Typescript. Includes vita and abstract. Includes bibliographical references (leaves 206-211). Also available for download via the World Wide Web; free to University of Oregon users. Address: http://wwwlib.umi.com/cr/uoregon/fullcit?p9948016.

Thesis (M. Sc.)--University of Canterbury, 2009. / Typescript (photocopy). Includes bibliographical references (leaves 128-130) and index. Also available via the World Wide Web.

Thesis (M. Sc.)--University of Canterbury, 2008. / Typescript (photocopy). Includes bibliographical references (p. 118-119). Also available via the World Wide Web.

We present the first dynamic algorithm that maintains a clique tree representation of a chordal graph and supports the following operations: (1) query whether deleting or inserting an arbitrary edge preserves chordality, (2) delete or insert an arbitrary edge, provided it preserves chordality. We give two implementations. In the first, each operation runs in O( n) time, where n is the number of vertices. In the second, an insertion query runs in O(log² n) time, an insertion in O(n) time, a deletion query in O(n) time, and a deletion in O(n log n) time. We also introduce the clique-separator graph representation of a chordal graph, which provides significantly more information about the graph's structure than the well-known clique tree representation. We present fundamental properties of the clique-separator graph and additional properties when the input graph is interval. We then introduce the train tree representation of interval graphs and use it to decide whether there is a certain linear ordering of the graph's maximal cliques. This yields a fully dynamic algorithm to recognize interval graphs in O(n log n) time per edge insertion or deletion. The clique-separator graph may lead to dynamic algorithms for every proper subclass of chordal graphs, and the train tree may lead to fast dynamic algorithms for problems on interval graphs. / Graduate

In numerous practical applications, it is necessary to find the smallest possible tree with a bounded diameter. A diameter-constrained minimum spanning tree (DCMST) of a given undirected, edge-weighted graph, G, is the smallest-weight spanning tree of all spanning trees of G which contain no path with more than k edges, where k is a given positive integer. The problem of finding a DCMST is NP-complete for all values of k; 4 ≤ k ≤ (n - 2), except when all edge-weights are identical. A DCMST is essential for the efficiency of various distributed mutual exclusion algorithms, where it can minimize the number of messages communicated among processors per critical section. It is also useful in linear lightwave networks, where it can minimize interference in the network by limiting the traffic in the network lines. Another practical application requiring a DCMST arises in data compression, where some algorithms compress a file utilizing a data-structure, and decompress a path in the tree to access a record. A DCMST helps such algorithms to be fast without sacrificing a lot of storage space. We present a survey of the literature on the DCMST problem, study the expected diameter of a random labeled tree, and present five new polynomial-time algorithms for an approximate DCMST. One of our new algorithms constructs approximate DCMST in a modified greedy fashion, employing a heuristic for selecting an edge to be added to the tree in each stage of the construction. Three other new algorithms start with an unconstrained minimum spanning tree, and iteratively refine it into an approximate DCMST. We also present ab algorithm designed for the special case when the diameter is required to be no more than 4. Such a diameter-4 tree is also used for evaluating the quality of other algorithms. All five algorithms were implemented on a PC, and four of them were also parallelized and implemented on a massively parallel machine-the MasPar MP-1. We discuss convergence, relative merits, and implementation of these heuristics. Our extensive empirical study shows that the heuristics produce good solutions for a wide variety of inputs.