Thesis (M.S.)--Ohio State University, 2008. / Title from first page of PDF file. Includes bibliographical references (p. 41-42).

<p>This thesis is concerned with a structure called the Reeb graph. There are three main problems considered. The first is devising an efficient algorithm for comnstructing the Reeb graph of a simplicial complex with respect to a generic simplex-wise linear real-valued function. We present an algorithm that builds the Reeb graph in almost optimal worst-case deterministic time. This was the first deterministic algorithm with the time bound which is linear up to a logarithmic factor. Without loss of generality, the complex is assumed to be 2-dimensional. The algorithm works by sweeping the function values and maintaining a spanning forest for the preimage, or the level-set, of the value. Using the observation that the operations that change the level-sets are off-line, we was able to achieve the above bound.</p><p>The second topic is the dynamic Reeb graphs. As the function changes its values, the Reeb graph also changes. We are interested in updating the Reeb graph. We reduce this problem to a graph problem that we call retroactive graph connectivity. We obtain algorithms for dynamic Reeb graphs, by using data structures that solve the graph problem. </p><p>The third topic is an argument regarding the complexity of computing Betti numbers. This problem is also related to the Reeb graph by means of the vertical Homology classes. The problem considered here is whether the realization of a simplicial complex in the Euclidean 4-space can result in an algorithm for computing its Homology groups faster than the usual matrix reduction methods. Using the observation that the vertical Betti numbers can always be computed more efficiently using the Reeb graph, we show that the answer to this question is in general negative. For instance, given a square matrix over the field with two elements, we construct a simplicial complex in linear time, realized in euclidean 4-space and a function on it, such that its Horizontal homology group, over the same field, is isomorphic with the null-space of the matrix. It follows that the Betti number computation for complexes realized in the 4-space is as hard as computing the rank for a sparse matrix.</p> / Dissertation

Leung, Kai Man. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2011. / Includes bibliographical references (leaves 63-68). / Abstracts in English and Chinese. / Chapter 1 --- Introduction --- p.1 / Chapter 2 --- Background --- p.5 / Chapter 2.1 --- Graph Connectivity --- p.5 / Chapter 2.1.1 --- Preliminaries --- p.5 / Chapter 2.1.2 --- Edge Connectivity --- p.7 / Chapter 2.1.3 --- Vertex Connectivity --- p.7 / Chapter 2.1.4 --- Algorithms for Graph Connectivities --- p.9 / Chapter 2.1.5 --- All Pairs Edge Connectivities --- p.10 / Chapter 2.1.6 --- Edge Splitting-off --- p.11 / Chapter 2.1.7 --- Graph Separator --- p.13 / Chapter 2.1.8 --- Expander Graphs --- p.15 / Chapter 2.1.9 --- Superconcentrator --- p.17 / Chapter 2.2 --- Network Coding --- p.19 / Chapter 2.2.1 --- Concept --- p.19 / Chapter 2.2.2 --- Linear Network Coding --- p.21 / Chapter 2.2.3 --- Random Linear Network Coding --- p.25 / Chapter 2.3 --- Algebraic Tools --- p.26 / Chapter 2.3.1 --- Linear Algebraic Algorithms --- p.26 / Chapter 2.3.2 --- Nested Dissection --- p.28 / Chapter 3 --- Algorithms for Graph Connectivities --- p.35 / Chapter 3.1 --- Introduction --- p.35 / Chapter 3.1.1 --- Our Results --- p.36 / Chapter 3.1.2 --- Related Work --- p.39 / Chapter 3.1.3 --- Techniques --- p.40 / Chapter 3.1.4 --- Organization --- p.41 / Chapter 3.2 --- New Algebraic Characterization --- p.41 / Chapter 3.3 --- Connectivities in Acyclic Graph --- p.46 / Chapter 3.3.1 --- Faster Encoding Algorithms --- p.47 / Chapter 3.4 --- Directed Planar Graphs --- p.49 / Chapter 3.5 --- All Pairs Edge Connectivities --- p.53 / Chapter 3.5.1 --- Connections with Previous Work --- p.55 / Chapter 3.6 --- Edge Splitting-off --- p.56 / Chapter 3.6.1 --- Edge Splitting-off in Directed Graphs --- p.57 / Chapter 3.6.2 --- Edge Splitting-off in Undirected Graphs --- p.58 / Concluding Remarks --- p.61 / Bibliography --- p.62

A celebrated theorem of Savitch [Savitch'70] states that NSPACE(S) is contained in DSPACE(S²). In particular, Savitch gave a deterministic algorithm to solve ST-Connectivity (an NL-complete problem) using O({log}²{n}) space, implying NL (non-deterministic logspace) is contained in DSPACE({log}²{n}). While Savitch's theorem itself has not been improved in the last four decades, several graph connectivity problems are shown to lie between L and NL, providing new insights into the space-bounded complexity classes. All the connectivity problems considered in the literature so far are essentially special cases of ST-Connectivity. In this dissertation, we initiate the study of auxiliary PDAs as graph connectivity problems and define sixteen different "graph realizability problems" and study their relationships. The complexity of these connectivity problems lie between L (logspace) and P (polynomial time). ST-Realizability, the most general graph realizability problem is P-complete. 1DSTREAL(poly), the most specific graph realizability problem is L-complete. As special cases of our graph realizability problems we define two natural problems, Balanced ST-Connectivity and Positive Balanced ST-Connectivity, that lie between L and NL. We study the space complexity of SGSLOGCFL, a graph realizability problem lying between L and LOGCFL. We define generalizations of graph squaring and transitive closure, present efficient parallel algorithms for SGSLOGCFL and use the techniques of Trifonov to show that SGSLOGCFL is contained in DSPACE(lognloglogn). This implies that Balanced ST-Connectivity is contained in DSPACE(lognloglogn). We conclude with several interesting new research directions.

A graph is k-resilient if it is possible to construct local routing tables for each vertex such that we can reach a specified destination vertex from anywhere in the graph. There is a conjecture that k-resilience is equivalent to (k+1)-connectivity. We prove this for 3-edge-connected graphs and 4-edge-connected planar triangulations. In the proof we use independent directed spanning trees. Two spanning trees are independent if they share no common edge with the same direction. For k=3,4 we show that a graph has k independent spanning trees if and only if it is k-edge-connected. We search for the spanning trees constructively through reductions of parts of the graph. Some of these reductions can also be used in a general k- connected case. Powered by TCPDF (www.tcpdf.org)

No description available.

Many digital models used in entertainment, medical visualization, material science, architecture, Geographic Information Systems (GIS), and mechanical Computer Aided Design (CAD) are defined in terms of their boundaries. These boundaries are often approximated using triangle meshes. The complexity of models, which can be measured by triangle count, increases rapidly with the precision of scanning technologies and with the need for higher resolution. An increase in mesh complexity results in an increase of storage requirement, which in turn increases the frequency of disk access or cache misses during mesh processing, and hence decreases performance. For example, in a test application involving a mesh with 55 million triangles in a machine with 4GB of memory versus a machine with 1GB of memory, performance decreases by a factor of about 6000 because of memory thrashing. To help reduce memory thrashing, we focus on decreasing the average storage requirement per triangle measured in 32-bit integer references per triangle (rpt). This thesis covers compact connectivity representation for triangle meshes and discusses four data structures: 1. Sorted Opposite Table (SOT), which uses 3 rpt and has been extended to support tetrahedral meshes. 2. Sorted Quad (SQuad), which uses about 2 rpt and has been extended to support streaming. 3. Laced Ring (LR), which uses about 1 rpt and offers an excellent compromise between storage compactness and performance of mesh traversal operators. 4. Zipper, an extension of LR, which uses about 6 bits per triangle (equivalently 0.19 rpt), therefore is the most compact representation. The triangle mesh data structures proposed in this thesis support the standard set of mesh connectivity operators introduced by the previously proposed Corner Table at an amortized constant time complexity. They can be constructed in linear time and space from the Corner Table or any equivalent representation. If geometry is stored as 16-bit coordinates, using Zipper instead of the Corner Table increases the size of the mesh that can be stored in core memory by a factor of about 8.

Graph augmentation concerns the addition of edges to a graph to satisfy some connectivity property of a graph. Previous research in this field has been preoccupied with edge augmentation; however the research in this document focuses on the addition of vertices to a graph to satisfy a specific connectivity property: ensuring that all the nodes of the graph are contained within cycles. A distinction is made between graph augmentation (edge addition), and graph enlargement (vertex addition). This document expands on previous research into a graph matching problem known as the “shoe matching problem” and the role of a graph enlargement algorithm in finding this solution. The aim of this research was to develop new and efficient algorithms to solve the graph enlargement problem as applied to the shoe matching problem and to improve on the naïve algorithm of Sanders. Three new algorithms focusing on graph enlargement and the shoe matching problem are presented, with positive results overall. The new enlargement algorithms: cost-optimised, matrix, and subgraph, succeeded in deriving the best result (least number of total nodes required) in 37%, 53%, and 57% of cases respectively (measured across 120 cases). In contrast, Sanders’s algorithm has a success rate of only 20%; thus the new algorithms have a varying success rate of approximately 2 to 3 times that of Sanders’s algorithm. / Computing / M. Sc. Computing

abstract: Measuring node centrality is a critical common denominator behind many important graph mining tasks. While the existing literature offers a wealth of different node centrality measures, it remains a daunting task on how to intervene the node centrality in a desired way. In this thesis, we study the problem of minimizing the centrality of one or more target nodes by edge operation. The heart of the proposed method is an accurate and efficient algorithm to estimate the impact of edge deletion on the spectrum of the underlying network, based on the observation that the edge deletion is essentially a local, sparse perturbation to the original network. Extensive experiments are conducted on a diverse set of real networks to demonstrate the effectiveness, efficiency and scalability of our approach. In particular, it is average of 260.95%, in terms of minimizing eigen-centrality, better than the standard matrix-perturbation based algorithm, with lower time complexity. / Dissertation/Thesis / Masters Thesis Computer Science 2016