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 71 for “"Graph connectivity"”.
-
On Pairwise Graph Connectivity
A graph on at least k+1 vertices is said to have global connectivity k if any two of its vertices are connected by k independent paths. The local connectivity of two vertices is the number of independent paths between those specific vertices. This dissertation is concerned with pairwise …
-
Efficiently computing graph similarity and graph connectivity
… their relationships can often be modeled as a graph G = (V,E) such that entities of interest are represented by vertices in V and their relationships are represented by edges in E. With the proliferation of graph applications, such as physics, chemistry, biology, social networks, information …
-
Cover Small Cuts and Flexible Graph Connectivity Problems
Given a graph with capacitated edges and a set of links on the same vertex set, the Cover Small Cuts problem aims to choose a minimum-cost link set such that for each cut with total edge capacity below a given threshold, at least one selected link covers that cut. We present examples and analysis …
-
Algorithm design and engineering for graph connectivity problems
… deals 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 …
-
Supertree construction with display graphs and dynamic graph connectivity
… efficient with the support of auxiliary display graphs and dynamic graph connectivity data structure. The agreement testing algorithm adds more requirements to compatibility testing problem. Given a profile $\P = \{\T_1, \T_2, \dots, \T_k\}$, the agreement testing problem asks whether an …
-
Graph connectivity and vector degree in motif-based graphs
Graph theory is frequently used to model and encode relationships in social networks, the internet, or biology. Due to the fundamental limitation that an edge can only connect two nodes, a standard graph is only capable of describing pairwise relationships. Therefore, some new models have been …
-
Viewing Trends in Graph Connectivity as Early Warnings of Epidemics and Vaccine Crises
… networks and the use of various statistical and graph theoretical tools. Using an agent-based model coupling a binary voting dynamic with an SIRVp model of infection, we simulate a vaccine preventable disease. Each week, agents are given the opportunity to change opinion to that of a friend, …
-
The Expanding Constant, Ramanujan Graphs, and Winnie Li Graphs
The expanding constant is a measure of graph connectivity that is important for certain applications. This paper discusses the mathematical foundations for the construction of Winnie Li's graphs and for the proof that Winnie Li's graphs are Ramanujan. The paper also establishes the implications of …
-
Realizable paths and the NL vs L problem
… 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 …
-
Algorithms for Solving Large Random Graphs
The problem of vertex colouring in large random graphs is unlikely to be an easy task. Given a number of available colours (in our study we used three colours), there are two relevant values of the graph connectivity delimiting three different states: when it is quite easy to find a solution, when …
-
A minimalist approach to deep multi-task learning
… (inputs to the model) are represented as graphs, i.e., collections of interconnected nodes. In '<i>Scaling GNNs to High-Dimensional Continuous Control</i>' and '<i>The Role of Morphology in Graph-Based Incompatible Control</i>', we learn a single control policy for agents of different …
-
LATENCY, CONDUCTANCE, AND THE ROLE OF CONNECTIVITY IN GRAPH PROBLEMS
In this thesis, we study how the connectivity of the underlying network graph affects a network's performance. We consider various aspects of graph connectivity determined by the structure of the graph and the distribution of latencies over the graph edges. Edge latency represents the time delay in …
-
Factoring Semiprimes Using PG2N Prime Graph Multiagent Search
… by multiagent depth-limited search of PG2N graphs is presented. An analysis of PG2Nn graph connectivity is used to generate heuristics for multiagent search. Further analysis is presented including the requirements on choosing prime numbers to generate 'hard' semiprimes; the lack of …
-
Parallel Algorithms for Processing Massive Texts and Graphs
… of the problem domain vary from social network graphs to DNA sequences. However, to address any problem subject to this restriction efficiently, we need alternative models of computation as the traditional RAM model is no longer an option. The main focus of our research is studying classical …
-
Learning Sparse Graph Laplacian with K Eigenvector Prior via Iterative GLASSO and Projection
Learning a suitable graph is an important precursor to many graph signal processing (GSP) tasks, such as graph signal compression and denoising. Previous graph learning algorithms either make assumptions on graph connectivity (e.g., graph sparsity), or make individual edge weight assumptions such …
-
Deep Learning-Based Part Labeling of Tree Components in Point Cloud Data
… different community detection methods and graph connectivity inference techniques, we demonstrate that K-NN connectivity inference and carefully selected community detection methods significantly enhance labeling accuracy, efficiency, and coverage. The proposed methods hold the potential to …
-
Deep Learning-Based Part Labeling of Tree Components in Point Cloud Data
… different community detection methods and graph connectivity inference techniques, we demonstrate that K-NN connectivity inference and carefully selected community detection methods significantly enhance labeling accuracy, efficiency, and coverage. The proposed methods hold the potential to …
Page 1 of 4