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"”.

  1. 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.

    uiuc Repository record for Vertex Connectivity of Graphs: Algorithms and Bounds (opens in a new tab)

  2. 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 …

    waterloo Repository record for Testing vertex connectivity of bowtie 1-plane graphs (opens in a new tab)

  3. 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 …

    uiuc Repository record for Survivable network design problems with element and vertex connectivity requirements (opens in a new tab)

  4. 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 …

    aalto Repository record for Vertex Connectivity via Local Computation: Breaking Quadratic Time, Poly-logarithmic Max-flows, and Derandomization (opens in a new tab)

  5. 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 …

    south-carolina Repository record for On Parallelization of Graph Algorithms, Performance Modelling and Autonomous 3D Printable Object Synthesis (opens in a new tab)

  6. 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 …

    jhu Repository record for A Combinatorial Analysis of the Eigenvalues of the Laplacian Matrices of Cographs (opens in a new tab)

  7. 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 …

    waterloo Repository record for Computing and Bounding the Scattering Number of Graphs (opens in a new tab)

  8. 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 …

    iastate Repository record for Techniques for determining equality of the maximum nullity and the zero forcing number of a graph (opens in a new tab)

  9. 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 …

    vt Repository record for Polyhedra:representation and recognition (opens in a new tab)

  10. 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 …

    oxford Repository record for Probing Mn-Mn and Mn-Si bonding in silicon cages (opens in a new tab)

  11. 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 …

    uiuc Repository record for Viewing extremal and structural problems through a probabilistic lens (opens in a new tab)

  12. 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 …

    uiuc Repository record for Node-weighted prize-collecting survivable network design problems (opens in a new tab)

  13. 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 …

    auckland-ms Repository record for Structure Mining: Finding Cohesive and Learning-Efficient Subgraphs (opens in a new tab)

  14. 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 …

    waterloo Repository record for Optimal Graph Streaming Algorithms and Further Advances in Modern Models of Computation (opens in a new tab)

  15. 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 …

    manitoba Repository record for Topology and geometry of chain, ribbon and tube silicates: generation and analysis of infinite one-dimensional arrangements of (TO4)n- tetrahedra (opens in a new tab)

  16. 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 …

    maryland Repository record for Robust design of wireless networks (opens in a new tab)

  17. 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 …

    ottawa-retro Repository record for Approximation Algorithms for Network Connectivity Problems (opens in a new tab)

  18. 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, …

    waterloo Repository record for Efficient Data Structures for Partial Orders, Range Modes, and Graph Cuts (opens in a new tab)

  19. 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 …

    ottawa-retro Repository record for On the 𝑘-Independence Number and Laplacian Toughness of Graphs (opens in a new tab)

  20. 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 …

    greece Repository record for Algorithm design and engineering for graph connectivity problems (opens in a new tab)