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 9 of 9 for “"Edge-connectivity"”.
-
Cut structures and randomized algorithms in edge-connectivity problems
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 1997.
-
A study of three-edge connectivity algorithms - Refinement and implementation
… quite a number of linear algorithms to compute 3-edge connected components of a multi-graph. In this thesis, we study the three most efficient algorithms and exclude other algorithms that are obviously inferior as they use different types of transformation in multiple phases. We present a data …
-
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 …
-
System for Collision Detection Between Deformable Models Built on Axis Aligned Bounding Boxes and GPU Based Culling
… deformations and deformations that preserve edge connectivity. We propose a new system built as a combination of Graphics Processing Unit (GPU) based culling and Axis Aligned Bounding Box (AABB) based culling. Techniques for performing hierarchy-less GPU-based culling are given. We then …
-
Matchings, Connectivity, and Eigenvalues in Regular Graphs
… $n$-vertex connected regular graphs in terms of edge-connectedness and determine when the matching number is minimized. We also establish the best upper bound for the number of cut-edges over $n$-vertex connected odd regular graphs and determine when the number of cut-edges is maximized. In …
-
Neural Representation for 3D Building Reconstruction from Point Clouds
… developed point completion network uses dynamic edge convolution and self-attention mechanism operations to extracts both local and global building shape information for complete building point set (BPS) reconstruction. This completion process mitigates the sparsity, occlusion, and point density …
-
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 …
-
Algorithms and complexity analyses for some combinational optimization problems
… graph G = (V, E), a non-negative cost for each edge, and a nonnegative connectivity requirement r_{uv} for every (unordered) pair of vertices u, v. The goal is to find a minimum-cost subgraph in which each pair of vertices u,v is joined by at least r_{uv} edge (vertex)-disjoint paths. A …
-
Topics in trivalent graphs
… introduces the usual linear algebra over GF2 of edge space E and its orthogonal subspaces Z (cycle space) and Z* (cut space). "Reduced vectors" are defined as elements of the quotient space E/Z*. Reduced vectors of edges give a simple way of characterising edges that are bridges (their reduced …