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 13 of 13 for “"Graph decomposition"”.
-
Distributed graph decomposition algorithms on Apache Spark
… analysis and mining of large and complex graphs for describing the characteristics of a vertex or an edge in the graph have widespread use in graph clustering, classification, and modeling. There are various methods for structural analysis of graphs including the discovery of frequent …
-
On vertex degrees, graph decomposition, and circular chromatic Ramsey number
… vertex degrees and a variant of Ramsey number of graphs, and also structural problems about graph decomposition. In a list (d_1,...,d_n) of positive integers, let r and s denote the largest and smallest entries. A list is gap-free if each integer between r and s is present. In Chapter 2, we prove …
-
Operads and moduli spaces
… moduli spaces, in particular deducing a Mobius graph decomposition of the moduli spaces of Klein surfaces, analogous to the ribbon graph decomposition of the moduli spaces of Riemann surfaces. We also begin a study, in generality, of quantum homotopy algebras, which arise as 'higher genus' …
-
On Induced Subgraphs, Degree Sequences, and Graph Structure
Finally, we define the A4-structure H of a graph G to be the 4-uniform hypergraph on the vertex set of G where four vertices comprise an edge in H if and only if they form the vertex set of an alternating 4-cycle in G. Our definition is a variation of the notion of the P4-structure, a hypergraph …
-
A factored planner for the temporal coordination of autonomous systems
… dividing the problem into a directed acyclic graph of factors via causal-graph decomposition and conquering each factor with heuristic forward search. Planning is guided by the DAG structure of the causal graph, and consists of a recursive element. All of the sub-goals for a particular factor …
-
The Limits of Recovering Planted Subgraphs
Given an arbitrary subgraph H = Hₙ and p = pₙ ∈ (0, 1), the planted subgraph model is defined as follows. A statistician observes the union of the “signal,” which is a random “planted” copy H* of H, together with random noise in the form of an instance of an Erdős–Rényi graph ´ G(n, p). Their goal …
-
Extremal problems on cycles, packing, and decomposition of graphs
… extremal problems concerning cycles and paths in graphs, graph packing, and graph decomposition. We use “graph” in the general sense, allowing loops and multi-edges. The Chv´atal–Erd˝os Theorem states that every graph whose connectivity is at least its independence number has a spanning cycle. In …
-
System reliability analysis methods for rapid multi-scale network risk assessment and decision making
… based algorithm, termed as a recursive decomposition algorithm (RDA), was recently proposed to identify disjoint cut sets and link sets and to compute the network reliability based on the identified sets, it is not feasible for a large-sized network because of the exponential program …
-
Excluding a Weakly 4-connected Minor
A 3-connected graph $G$ is called weakly 4-connected if min $(|E(G_1)|, |E(G_2)|) \leq 4$ holds for all 3-separations $(G_1,G_2)$ of $G$. A 3-connected graph $G$ is called quasi 4-connected if min $(|V(G_1)|, |V(G_2)|) \leq 4$. We first discuss how to decompose a 3-connected graph into quasi …
-
Decompositions of Mixed Graphs with Partial Orientations of the P<sub>4</sub>.
<p>A decomposition <em>D</em> of a graph <em>H</em> by a graph <em>G</em> is a partition of the edge set of <em>H</em> such that the subgraph induced by the edges in each part of the partition is isomorphic to <em>G</em>. A <em>mixed graph</em> on <em>V</em> vertices is an ordered pair …
-
Tricyclic Steiner Triple Systems with 1-Rotational Subsystems.
… it admits an automorphism whose disjoint cyclic decomposition consists of three cycles. In this thesis we give necessary and sufficient conditions for the existence of a tricyclic <em>STS</em>(<em>v</em>) when one of the cycles is of length one. In this case, the <em>STS</em>(<em>v</em>) will …
-
Packings and Coverings of Complete Graphs with a Hole with the 4-Cycle with a Pendant Edge
… packings and coverings of various complete graphs with the 4-cycle with a pendant edge. We consider both restricted and unrestricted coverings. Necessary and sufficient conditions are given for such structures for (1) complete graphs K<sub>v, </sub>(2) complete bipartite graphs …