Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 20 of 20 for “"Vertex connectivity"”.
-
Vertex Connectivity of Graphs: Algorithms and Bounds
This thesis concerns several problems concerning vertex connectivity of undirected graphs and presents new bounds and algorithms for these problems.
-
Testing vertex connectivity of bowtie 1-plane graphs
… of a minimum separating set of $G$ is called the vertex connectivity of $G$. A separating set of $G$ that is a cycle is called a separating cycle of $G$. Let $G$ be a planar graph with a given planar embedding. Let $\Lambda(G)$ be a supergraph of $G$ obtained by inserting a face vertex in each …
-
Survivable network design problems with element and vertex connectivity requirements
… this thesis, we consider degree-bounded element-connectivity Survivable Network Design Problem (Elem-SNDP) and degree-bounded Rooted k-outconnectivity Problem. We suggest bicriteria approximation algorithms that are motivated by Ene and Vakilian's work in [1] and Lau and Zhou's work in [2]. The …
-
Vertex Connectivity via Local Computation: Breaking Quadratic Time, Poly-logarithmic Max-flows, and Derandomization
Vertex connectivity is a classic graph-theoretic notion, that roughly measures the robustness of a network against vertex failure. Vertex connectivity k of an n-vertex m-edge graph is the minimum number of vertices to be removed to disconnect the graph. A major open problem asked almost 50 years …
-
On Parallelization of Graph Algorithms, Performance Modelling and Autonomous 3D Printable Object Synthesis
… applications. The first area is concerned with k-vertex connectivity in graph theory, the second area deals performance evaluation using extended roofline models for GPU parallel applications and finally the third problem area is related to synthesis 3D printable objects from 2D images. In this …
-
A Combinatorial Analysis of the Eigenvalues of the Laplacian Matrices of Cographs
… defined class of graphs built from a single vertex by the operations of disjoint union and join. The eigenvalues of a cograph's Laplacian matrix are nonnegative integers. In this thesis, we explore the combinatorial significance of cograph Laplacian eigenvalues. We show that the second …
-
Computing and Bounding the Scattering Number of Graphs
… scattering number of planar graphs with given vertex-connectivity and minimum degree. These are generalizations of lower bounds on the matching number of such graphs obtained by Baybars and Nishizeki in 1979 and our proof strategy is strongly inspired by theirs. We further generalize these …
-
Techniques for determining equality of the maximum nullity and the zero forcing number of a graph
… are a Colin de Verdi\'ere type parameter and the vertex connectivity. We also use matrices, such as a divisor matrix of a graph and an equitable partition of the adjacency matrix of a graph, to establish a lower bound for the nullity of the graph's adjacency matrix. Last, we introduce a new graph …
-
Polyhedra:representation and recognition
… our representation is not a strict dual of the vertex connectivity graph, and hence is not necessarily ambiguous. However, we have not been able to prove that the representation is unambiguous. An augmented dual spherical representation which is unique for general polyhedra is presented. This …
-
Probing Mn-Mn and Mn-Si bonding in silicon cages
… functionals stabilise structures with low vertex connectivity while others tend to favour deltahedral frameworks. Multiconfigurational self-consistent field theory (MC-SCF) has been used to get an alternative perspective on bonding in these clusters. By making use of generalised and …
-
Viewing extremal and structural problems through a probabilistic lens
… asked whether a similar phenomenon holds for vertex-connectivity; more precisely: is there an integer-valued function $f(k)$ such that every $f(k)$-connected graph admits a spanning, bipartite $k$-connected subgraph? In Chapter 4, as in joint work with Ferber, we show that every $10^{10}k^3 …
-
Node-weighted prize-collecting survivable network design problems
… undirected graph $G=(V,E)$ and integral connectivity requirements $r(st)$ for each pair of nodes $st$. The goal is to find a minimum node-weighted subgraph $H$ of $G$ such that, for each pair $st$, $H$ contains $r(st)$ \emph{disjoint} paths between $s$ and $t$. PC-SNDP is a generalization …
-
Structure Mining: Finding Cohesive and Learning-Efficient Subgraphs
… perturbations without compromising its core connectivity or functionality. To identify subgraphs characterized by high co-occurrence and robustness, this thesis delves into the mining of cohesive subgraphs and learning-efficient subgraphs. Cohesive subgraphs encompass both co-occurrence and …
-
Optimal Graph Streaming Algorithms and Further Advances in Modern Models of Computation
… setting. We study approximate minimum cut, k-vertex connectivity, maximum matching, minimum vertex cover, and correlation clustering across different streaming models—including insertion-only, dynamic, and random-order streams. By establishing tight upper and lower bounds—often matching up to …
-
Topology and geometry of chain, ribbon and tube silicates: generation and analysis of infinite one-dimensional arrangements of (TO4)n- tetrahedra
… classes and sub-classes based the number and connectivity of tetrahedra or vertices in the repeat unit (unit cell) of each chain arrangement. Chain graphs that correspond to the most abundant minerals have O:T = 3:1 - 2.75:1 and chains with O:T < 2.5:1 – 2:1 are not observed in minerals …
-
Robust design of wireless networks
… graph is k-connected. We consider both edge and vertex connectivity. The problem is NP-hard. We develop approximation algorithms that find close to optimal solutions. We consider extension to higher dimensions, and provide approximation guarantees for the algorithms. In addition, our methods …
-
Approximation Algorithms for Network Connectivity Problems
In this dissertation, we examine specific network connectivity problems, and achieve improved approximation algorithm and integrality gap results for them. We introduce an important new, highly useful and applicable, network connectivity problem - the Vital Core Connectivity Problem (VCC). Despite …
-
Efficient Data Structures for Partial Orders, Range Modes, and Graph Cuts
… data structure for dynamic 2- and 3- edge and vertex connectivity. Here, the data structure is given the entire sequence of operations in advance, and the dynamic operations are edge insertion and removal. Finally, we give a simplification of Karger's near-linear time minimum cut algorithm, …
-
On the 𝑘-Independence Number and Laplacian Toughness of Graphs
… work focuses on themes of independence number, connectivity, graph toughness, and closed walks in infinite regular trees. Computing the 𝑘-independence number of a graph, which is the size of a largest set of vertices that are a distance greater than 𝑘 apart in the graph, is NP-complete. In other …
-
Algorithm design and engineering for graph connectivity problems
… with topics related to some notions of graph connectivity in directed graphs and mixed graphs. The edge and vertex connectivity of a graph are important measures of its resilience as a network. There is a great variety of real-life relations that can be modeled by graphs. A few of the most …