Thesis (M. Phil.)--University of Hong Kong, 1997. / Includes bibliographical references (leaf 83-84).

Thesis (M. Phil.)--University of Hong Kong, 1997. / Includes bibliographical references (leaf 74-76).

Thesis (M.S.)--The University of North Carolina at Greensboro, 2008. / Directed by Paul Duvall; submitted to the Dept. of Mathematical Sciences. Title from PDF t.p. (viewed Sep. 4, 2009). Includes bibliographical references (p. 57).

No description available.

The concept of a tree has been used in various areas of mathematics for over a century. In particular, trees appear to be one of the most fundamental notions in computer science. Sequential algorithms for trees are generally well studied. Unfortunately many of these sequential algorithms use methods which seem to be inherently sequential. One of the contributions of this thesis is the introduction of several parallel techniques for the construction of various types of trees and the presentation of new parallel tree construction algorithms using these methods. Along with the parallel tree construction techniques presented here, we develop techniques which have broader applications. We use the Parallel Random Access Machine as our model of computation. We consider two basic methods of constructing trees:tree expansion and tree synthesis. In the tree expansion method, we start with a single vertex and construct a tree by adding nodes of degree one and/or by subdividing edges. We use the parallel tree expansion technique to construct the tree representation for graphs in the family of graphs known as cographs. In the tree synthesis method, we start with a forest of single node subtrees and construct a tree by adding edges or (for rooted trees) by creating parent nodes for some roots of the trees in the forest. We present a family of parallel and sequential algorithms to construct various approximations to the Huffman tree. All these algorithms apply the tree synthesis method by constructing a tree in a level-by-level fashion. To support one of the algorithms in the family we develop a technique which we call the cascading sampling technique. One might suspect that the parallel tree synthesis method can be applied only to trees of polylogarithmic height, but this is not the case.We present a technique which we call the valley filling technique and develop its accelerated version called the accelerated valley filling technique. We present an application of this technique to an optimal parallel algorithm for construction of minimax trees. / Science, Faculty of / Computer Science, Department of / Graduate

No description available.

Recent advances in linear programming solution methodology have focused on interior point algorithms. These are powerful new methods, achieving significant reductions in computer time for large LPs and solving problems significantly larger than previously possible. This dissertation describes the implementation of interior point algorithms. It focuses on applications of direct sparse matrix methods to sparse symmetric positive definite systems of linear equations on scalar computers and vector supercomputers. The most computationally intensive step in each iteration of any interior point algorithm is the numerical factorization of a sparse symmetric positive definite matrix. In large problems or relatively dense problems, 80-90% or more of computational time is spent in this step. This study concentrates on solution methods for such linear systems. It is based on modifications and extensions of graph theory applied to sparse matrices. The row and column permutation of a sparse symmetric positive definite matrix dramatically affects the performance of solution algorithms. Various reordering methods are considered to find the best ordering for various numerical factorization methods and computer architectures. It is assumed that the reordering method will follow the fill-preserving rule, i.e., not allow additional fill-ins beyond that provided by the initial ordering. To follow this rule, a modular approach is used. In this approach, the matrix is first permuted by using any minimum degree heuristic, and then the permuted matrix is again reordered according to a specific reordering objective. Results of different reordering methods are described. There are several ways to compute the Cholesky factor of a symmetric positive definite matrix. A column Cholesky algorithm is a popular method for dense and sparse matrix factorization on serial and parallel computers. Applying this algorithm to a sparse matrix requires the use of sparse vector operations. Graph theory is applied to reduce sparse vector computations. A second and relatively new algorithm is the multifrontal algorithm. This method uses dense operations for sparse matrix computation at the expense of some data manipulation. The performance of the column Cholesky and multifrontal algorithms in the numerical factorization of a sparse symmetric positive definite matrix on an IBM 3090 vector supercomputer is described.

No description available.

Yang, Lin. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2009. / Includes bibliographical references (leaves 57-61). / Abstract also in Chinese. / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Problems and Main Results --- p.2 / Chapter 1.1.1 --- Firefighting on Trees --- p.2 / Chapter 1.1.2 --- Maximum k-Vertex Cover on Trees --- p.3 / Chapter 1.2 --- Background --- p.3 / Chapter 1.2.1 --- Random Separation --- p.4 / Chapter 1.2.2 --- Kernelization --- p.5 / Chapter 1.2.3 --- Infeasibility of Polynomial Kernel --- p.6 / Chapter 1.3 --- Organization of the Thesis --- p.7 / Chapter 2 --- Firefighting on Trees --- p.9 / Chapter 2.1 --- Definitions and Notation --- p.10 / Chapter 2.2 --- FPT Algorithms --- p.13 / Chapter 2.2.1 --- Saving k Vertices --- p.14 / Chapter 2.2.2 --- Saving k Leaves --- p.19 / Chapter 2.2.3 --- Protecting k Vertices --- p.23 / Chapter 2.3 --- Approximation --- p.29 / Chapter 2.3.1 --- A (1 ´ؤ 1/e)-Approximation Algorithm --- p.29 / Chapter 2.3.2 --- LP-Repsecting Rounding cannot Do Better --- p.33 / Chapter 3 --- Maximum k-Vertex Cover on Trees --- p.38 / Chapter 3.1 --- Maximum k Vertex Cover on Trees --- p.39 / Chapter 3.2 --- k-MVC on Degree Bounded Graphs --- p.45 / Chapter 3.3 --- k-MVC on Degeneracy Bounded Graphs --- p.46 / Chapter 3.4 --- Extension to Maximum k Dominating Set --- p.47 / Chapter 4 --- Conclusion --- p.49 / Chapter 4.1 --- The Firefighter problem --- p.49 / Chapter 4.2 --- The Maximum k-Vertex Cover problem --- p.53 / Acknowledgement --- p.55 / Bibliography --- p.57

Thesis (Ph. D.)--Ohio State University, 2006. / Title from first page of PDF file. Includes bibliographical references (p. 107-113).