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 15 of 15 for “"Multigraph"”.
-
Extremal Results and Algorithms for Degree Sequences of Graphs
A 2-multigraph is a loopless multigraph with maximum multiplicity 2; pairs of vertices induce 0, 1, or 2 edges. A 2-multigraph is parsimonious if it has the minimum number of single edges (multiplicity 1) among all 2-multigraphs with the same degree sequence. In every parsimonious 2-multigraph, the …
-
Problems in Extremal Graph Theory
What is the maximum number of edges in a multigraph on n vertices if every k-set spans at most r edges? We asymptotically determine this maximum for almost all k and r as n tends to infinity, thus giving a generalization of Turan's theorem. We find exact answers in many cases, even when edges of …
-
Edge-choosability of Planar Graphs
… to the List Colouring Conjecture, if G is a multigraph then χ' (G)=χl' (G) . In this thesis, we discuss a relaxed version of this conjecture that every simple graph G is edge-(∆ + 1)-choosable as by Vizing’s Theorem ∆(G) ≤χ' (G)≤∆(G) + 1. We prove that if G is a planar graph without 7-cycles …
-
Keystroke dynamics as a biometric
… the design, development and deployment of the multigraph-based BAKER software platform, a system for collecting statistical GFT data from live environments. This software platform has enabled the collection of an extensive set of keystroke biometric data for a group of participating computer …
-
Sufficient degree conditions for graph embeddings
… problem of finding k vertex-disjoint cycles in a multigraph. This problem originated from a conjecture of Erdos and has led to many different results. Corradi and Hajnal looked at a minimum degree condition. Enomoto and Wang independently looked at a minimum degree-sum condition. More recently, …
-
GRAPH-BASED METHODS FOR PATH PLANNING WITH DYNAMIC OBSTACLES USING LINEAR TEMPORAL LOGIC
… one of the shortest paths for the mission The Multigraph Network Planning method and the Critical Path method can find all the possible paths with predetermined path length. The Random Walk method required more computational effort and memory compared to the other three methods.
-
Precise Partitions Of Large Graphs
… for the existence of a subdivision of a multigraph in which some of the vertices are specified and the distance between each pair of vertices in the subdivision is prescribed (within one).</p>
-
A Predictive Model Which Uses Descriptors of RNA Secondary Structures Derived from Graph Theory.
… RNA structures; however, in this research, a multigraph representation of RNA is used, in which vertices represent stems and edges represent the internal motifs. Any type of RNA secondary structure may be represented by a graph in this manner. We define novel graphical invariants to quantify …
-
Managing interprocedural optimization
… algorithm is developed for constructing the call multigraph, the underlying program representation for interprocedural optimization. A procedure cloning algorithm is also described. This algorithm avoids the significant code growth and increased compilation time possible with cloning, while …
-
Algorithms for Simple Stochastic Games
… game (SSG) is a game defined on a directed multigraph and played between players MAX and MIN. Both players have control over disjoint subsets of vertices: player MAX controls a subset VMAX and player MIN controls a subset VMIN of vertices. The remaining vertices fall into either VAVE, a …
-
Extremal Theory of Graph Minors and Related Topics
… which introduces the new notion of containing a multigraph as a minor. The extremal function is asymptotically derived for multigraphs rKt, consisting of t vertices and all pairs having multiplicity r, in two regimes corresponding to r = ω(log t) or r = o(log t). A lower bound is proven for all r …
-
Hamiltonian cycle and related problems : vertex-breaking, grid graphs, and Rubik's Cubes
… Tree-Residue Vertex-Breaking (TRVB). Given a multigraph G some of whose vertices are marked "breakable," TRVB asks whether it is possible to convert G into a tree via a sequence of applications of the vertex-breaking operation: disconnecting the edges at a degree-G breakable vertex by …
-
Stability and Spectral Properties in the Max Algebra with Applications in Ranking Schemes
… to the max algebra. Using the concept of a multigraph, we prove that a number of inequalities related to the spectral radius of a matrix polynomial are also true for its largest max eigenvalue. We are next concerned with the asymptotic stability of non-negative matrices in the context of …
-
Generalized multi-commodity network flows : case studies in space logistics and complex infrastructure systems
… and multiple edges between the same end nodes (multigraph). With this modification, the model can handle multiple commodities that interact with each other in the form of requirement at nodes, transformation on edges, and concurrency within edges. A linear programming (LP) formulation and a …
-
Algoritmi avanzati per il Subgraph Isomorphism, Motif Discovery, e Graph Embedding su reti complesse
… questo approccio ai dati multi-relazionali, MultiGraphMatch affronta il problema del matching in multigrafi, introducendo una struttura di indicizzazione a firma di bit per gestire in modo efficiente relazioni complesse tra gli archi. Per i grafi dinamici, introduciamo MODIT, un approccio …