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 48 for “"geometric graph"”.
-
Geometric Graph Theory and Wireless Sensor Networks
In this work, we apply geometric and combinatorial methods to explore a variety of problems motivated by wireless sensor networks. Imagine sensors capable of communicating along straight lines except through obstacles like buildings or barriers, such that the communication network topology of the …
-
MANIFOLD FILTERS AND NEURAL NETWORKS: GEOMETRIC GRAPH SIGNAL PROCESSING IN THE LIMIT
Graph Neural Networks (GNNs) are the tool of choice for scalable and stable learning in graph-structured data applications involving geometric information. In this thesis, we address the fundamental questions of how GNNs can generalize across different graph scales and how they can remain stable on …
-
Initial Solution Improvements to a Tethered Robotic Path Planner using Random Geometric Graph Configurations and Biased Sampling
… The second re-configures the underlying Random Geometric Graph to form edges using a $k$-nearest neighbor approach, allowing longer edges to be evaluated. Both of these methods are thoroughly tested on a series of five maps, three of which are generated using a pipeline involving Blender and …
-
Topics in Stochastic Combinatorial Optimization and Extremal Graph Theory
We consider a random geometric graph, G(n, r ), constructed by placing points randomly in a square S n of area n according to a Poisson process of intensity 1, and adding an edge joining any pair of points at most distance r=r(n) apart according to the ℓinfinity -metric. We show that w.h.p. …
-
Γεωμετρικά γραφήματα με y-μονότονα και xy-μονότονα μονοπάτια: κατασκευή και αναγνώριση
… points of P which are called the roots of P. A geometric graph G = (P,E) is called k−rooted if P is k−rooted and its roots are the roots of P. A geometric path Q = (q_0, q_1, ..., q_t) is called y−monotone if the sequence of the y−coordinates of the points of Q, i.e. the sequence y(q_0), y(q_1), …
-
Turn Constrained Path Planning Problems
… a source point s to a target point t in a geometric graph. We require that the paths do not have any sharp turn angles. We present a review of turn constrained path planning algorithms and also algorithms for constructing disjoint paths. We then combine these techniques and present an …
-
Data Transmission in Quantized Consensus
… average. Besides, it works on all types of graphs (star, complete, ring, random geometric graph). My other algorithm, distributing averaging algorithm (PQDA) with probabilistic quantization also works on random geometric graph, star, ring and slow co-herency graph. It shows significant …
-
Matchings in Geometric Graphs
A geometric graph is a graph whose vertex set is a set of points in the plane and whose edge set contains straight-line segments. A matching in a graph is a subset of edges of the graph with no shared vertices. A matching is called perfect if it matches all the vertices of the underling graph. A …
-
Random combinatorial processes
… for Wishart matrices, a model of a random geometric graph; the Boolean intersection model, an intersection of random sets in $\mathbb{R}^d$; and rumor spreading algorithms on the $d$-regular tree.
-
Disjoint paths in geometric graphs
… shortest paths connecting two given nodes in a geometric graph is the quintessential problem in computational geometry. We consider several variations of this problem with applications that include robotics, Geographic Information Systems, and sensor networks. The first problem we address is the …
-
A generalization of the face routing algorithm to some non-planar networks
… for them. Routing algorithms which use the geographical location information of nodes are called position-based routing algorithms. In such algorithms, the ad hoc network is modeled as a geometric graph known as the unit disk graph. The FACE ROUTING algorithm is one such position-based routing …
-
Bootstrap Percolation on Random Geometric Graphs
… or disease across the vertex set of a graph. It was introduced in 1979 by Chalupa, Leith and Reich as a simple model of dynamics of ferromagnetism. We consider the following version of this process:Initially, each vertex of the graph is set active with probability p or inactive …
-
Local geometric routing algorithms for edge-augmented planar graphs
Given a geometric graph G = (V,E), where V is the set of vertices and E is the set of edges and a source-target pair {s,t} is a subset of V, a local geometric routing algorithm seeks a route from s to t using only local neighborhood relationships. This thesis proposes a local geometric routing …
-
Geometric and Algebraic Graphs and their Applications
… and their chemical property which creates a geometric graph that we can analyze. Then we take a look at a classic conjecture colloquially known as "The Middle Two Levels Conjecture." This problem in pure graph theory involves finding Hamiltonian cycles in a power set on n elements. We take …
-
On non-stationary Wishart matrices and functional Gaussian approximations in Hilbert spaces
… for an edge-counting statistic of a random geometric graph.
-
On path-greedy geometric spanners
A t-spanner is a graph in which the shortest path between two vertices never exceeds t times the distance between the two nodes – a t-approximation of the complete graph. A geometric graph is one in which its vertices are points with defined coordinates and the edges correspond to line segments …
-
Homological Spanning Forests for Discrete Objects
… classification, pattern recognition, geometric modelling, etc. The homology of digital objects is an algebraic notion that provides a concise description of their topology in terms of connected components, tunnels and cavities. The purpose of this work is to develop a theoretical and …
Page 1 of 3