Fung, Wai Shing. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2009. / Includes bibliographical references (leaves 70-76). / Abstract also in Chinese. / Abstract --- p.i / Acknowledgement --- p.iii / Chapter 1 --- Overview --- p.1 / Chapter 1.1 --- Background --- p.1 / Chapter 1.1.1 --- Network Design --- p.1 / Chapter 1.1.2 --- Degree Bounded Network Design --- p.3 / Chapter 1.1.3 --- Degree Bounded Vertex Connectivity Network Design --- p.6 / Chapter 1.2 --- Our Results --- p.7 / Chapter 1.2.1 --- Problem Definition --- p.8 / Chapter 1.2.2 --- Main Result --- p.8 / Chapter 1.2.3 --- Organization of This Thesis --- p.9 / Chapter 1.3 --- Algorithm Outline --- p.10 / Chapter 1.3.1 --- Christofides' Algorithm for TSP --- p.10 / Chapter 1.3.2 --- Extending Christofides´ة Algorithm to K > 2 --- p.12 / Chapter 1.3.3 --- Bienstock et al´ةs Splitting-Off Theorem --- p.13 / Chapter 2 --- Basics --- p.18 / Chapter 2.1 --- Notations and Terminology --- p.18 / Chapter 2.2 --- .Menger's Theorem --- p.20 / Chapter 2.3 --- Submodular Functions --- p.21 / Chapter 2.4 --- Use of Submodularity in Proofs of Splitting-Off Theorems --- p.22 / Chapter 2.5 --- Splitting-Off Concerning Edge Connectivity --- p.27 / Chapter 2.6 --- Splitting-Off Concerning Vertex Connectivity --- p.30 / Chapter 2.7 --- Vertex Connectivity Network Design --- p.32 / Chapter 2.7.1 --- Rooted Connectivity --- p.33 / Chapter 2.7.2 --- Global Connectivity --- p.35 / Chapter 2.7.3 --- Generalized Steiner Network --- p.36 / Chapter 2.8 --- Network Design with Metric Cost --- p.37 / Chapter 2.8.1 --- Minimum Cost K-Vertex-Connected Subgraph --- p.38 / Chapter 2.8.2 --- Degree Bounded Minimum Spanning Tree --- p.40 / Chapter 3 --- Minimum Degree K-Vertex-Connected Subgraph --- p.42 / Chapter 3.1 --- Preliminary --- p.44 / Chapter 3.1.1 --- Tight Sets --- p.44 / Chapter 3.1.2 --- (xxi)-Critical Sets --- p.46 / Chapter 3.2 --- Splitting-Off with Parallel Edges --- p.47 / Chapter 3.2.1 --- When Does Replacement Fail? --- p.48 / Chapter 3.2.2 --- Deriving a Special Structure --- p.50 / Chapter 3.2.3 --- Such Structure Is Impossible --- p.50 / Chapter 3.3 --- Splitting-Off with Redundant Edges --- p.50 / Chapter 3.3.1 --- Proof Outline --- p.51 / Chapter 3.3.2 --- When Does Splitting-Off Fail? --- p.54 / Chapter 3.3.3 --- Admissible Pairs Exists If Two Redundant Edges Are Present --- p.57 / Chapter 3.3.4 --- Proof of Property(T*) --- p.58 / Chapter 3.3.5 --- Existence of Jointly Admissible Pairs --- p.62 / Chapter 3.4 --- Main Algorithm --- p.66 / Chapter 4 --- Concluding Remarks --- p.69 / Bibliography --- p.70

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

Cheung, Yat Ming. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2010. / Includes bibliographical references (leaves 75-78). / Abstracts in English and Chinese. / Chapter 1 --- Introduction --- p.6 / Chapter 2 --- Symplectic Geometry and Special Lagrangian Graphs in Cn --- p.10 / Chapter 2.1 --- Symplectic and Lagrangian Geometry of Cn --- p.10 / Chapter 2.2 --- Calibrated and Spccial Lagrangian Geometries in Cn --- p.13 / Chapter 2.3 --- Special Lagrangian Differential Equation --- p.16 / Chapter 3 --- Contact Geometry in S2n-1 --- p.20 / Chapter 3.1 --- Contact and Legendrian Geometries in S2n-1 --- p.20 / Chapter 3.2 --- Special Lagrangian Cone in R2n --- p.24 / Chapter 3.3 --- The Second Fundamental Form of Lagrangian Cone in E2n --- p.26 / Chapter 4 --- Geometry of Grassmannians --- p.29 / Chapter 4.1 --- Locally Symmetric Space --- p.29 / Chapter 4.2 --- "The Grassmann manifold G(n, m)" --- p.33 / Chapter 4.3 --- "Leichtweiss' Formula for Curvature Tensor in G(n, m)" --- p.36 / Chapter 4.4 --- "Normal Neighbourhoods of a Point in G(n, m)" --- p.39 / Chapter 4.5 --- Some Remarks on Lagrangian Grassmannians --- p.49 / Chapter 5 --- Harmonic Maps between Riemannian Manifolds --- p.51 / Chapter 5.1 --- Energy Functional and Tension Field --- p.52 / Chapter 5.2 --- Harmonic Map and Euler-Lagrange Equation --- p.56 / Chapter 5.3 --- The Gauss Map and its Tension Field --- p.59 / Chapter 5.4 --- Simple Riemannian Manifolds and A Liouville-Type Result of Har- monic Maps --- p.63 / Chapter 6 --- Bernstein-Type Results for Special Lagrangian Graphs --- p.65 / Chapter 6.1 --- Convexity and Bounded Slope Assumption --- p.65 / Chapter 6.2 --- Spherical Bernstein-Type Result --- p.68 / Chapter 6.3 --- Bernstein-Type Result with only Bounded Slope --- p.72 / Bibliography --- p.75

Chan, Ho Fai. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2008. / Includes bibliographical references (leaves 59-60). / Abstracts in English and Chinese. / Chapter 1 --- Introduction --- p.5 / Chapter 2 --- Current methods on Neighbor-Joining --- p.9 / Chapter 2.1 --- Introduction to graph theory --- p.9 / Chapter 2.2 --- General discussion on visualizing distance matrices by binary trees --- p.18 / Chapter 2.3 --- Original 0(N5) Neighbor-Joining algorithm --- p.21 / Chapter 2.4 --- Speedup of NJ --- p.22 / Chapter 2.4.1 --- 0(N3) NJ for arbitrary distance matrices --- p.23 / Chapter 2.4.2 --- 0(N2) NJ on additive matrices --- p.23 / Chapter 3 --- Finding neighbor pairs --- p.25 / Chapter 3.1 --- Properties of Binary trees --- p.25 / Chapter 3.2 --- Similar rows: finding all neighbor pairs in additive matrices --- p.28 / Chapter 4 --- Divide-and-Conquer Neighbor-Joining --- p.35 / Chapter 4.1 --- DCNJ Algorithm --- p.36 / Chapter 4.2 --- Theories of DCNJ on additive matrices: Correctness and Complexity --- p.44 / Chapter 5 --- Experimental Results --- p.56 / Chapter 6 --- Conclusions --- p.58

The eccentricity of a vertex, v, of a connected graph, G, is the distance to a furthest vertex from v. A mode vertex of a connected graph, G, is a vertex whose eccentricity occurs as often in the eccentricity sequence of G as the eccentricity of any other vertex. The mode of a graph, G, is the subgraph induced by the mode vertices of G. A mode graph is a connected graph for which each vertex is a mode vertex. Note that mode graphs are a generalization of self-centered graphs. This paper presents some results based on these definitions.

For a graph G = (V;E), a pebble distribution is defined as a mapping of the vertex set in to the integers, where each vertex begins with f(v) pebbles. A pebbling move takes two pebbles from some vertex adjacent to v and places one pebble on v. A rubbling move takes one pebble from each of two vertices that are adjacent to v and places one pebble on v. A vertex x is reachable under a pebbling distribution f if there exists some sequence of rubbling and pebbling moves that places a pebble on x. A pebbling distribution where every vertex is reachable is called a rubbling configuration. The t-restricted optimal rubbling number of G is the minimum number of pebbles required for a rubbling configuration where no vertex is initially assigned more than t pebbles. Here we present results on the 1-restricted optimal rubbling number and the 2- restricted optimal rubbling number.

A labeling of a graph is an assignment of a natural number to each vertex of a graph. Graceful labelings are very important types of labelings. The study of graceful labelings is very difficult and little has been shown about such labelings. Vertex-relaxed graceful labelings of graphs are a class of labelings that include graceful labelings, and their study gives an approach to the study of graceful labelings. In this thesis we generalize the congruence approach of Rosa to obtain new criteria for vertex-relaxed graceful labelings of graphs. To do this, we generalize Faulhaber’s Formula, which is a famous result about sums of powers of integers.

Irwin Mark Jacobs. / "September 15, 1959." Issued also as a thesis, M.I.T. Dept. of Electrical Engineering, August 21, 1959. / Bibliography: p. 61-62. / Army Signal Corps Contract DA36-039-sc-78108. Dept. of the Army Task 3-99-20-001 and Project 3-99-00-000.

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

This thesis is devoted to the analysis of a class of iterative probabilistic algorithms in regular graphs, called locally greedy algorithms, which will provide bounds for graph functions in regular graphs with large girth. This class is useful because, by conveniently setting the parameters associated with it, we may derive algorithms for some well-known graph problems, such as algorithms to find a large independent set, a large induced forest, or even a small dominating set in an input graph G. The name ``locally greedy" comes from the fact that, in an algorithm of this class, the probability associated with the random selection of a vertex v is determined by the current state of the vertices within some fixed distance of v. Given r > 2 and an r-regular graph G, we determine the expected performance of a locally greedy algorithm in G, depending on the girth g of the input and on the degree r of its vertices. When the girth of the graph is sufficiently large, this analysis leads to new lower bounds on the independence number of G and on the maximum number of vertices in an induced forest in G, which, in both cases, improve the bounds previously known. It also implies bounds on the same functions in graphs with large girth and maximum degree r and in random regular graphs. As a matter of fact, the asymptotic lower bounds on the cardinality of a maximum induced forest in a random regular graph improve earlier bounds, while, for independent sets, our bounds coincide with asymptotic lower bounds first obtained by Wormald. Our result provides an alternative proof of these bounds which avoids sharp concentration arguments. The main contribution of this work lies in the method presented rather than in these particular new bounds. This method allows us, in some sense, to directly analyse prioritised algorithms in regular graphs, so that the class of locally greedy algorithms, or slight modifications thereof, may be applied to a wider range of problems in regular graphs with large girth.