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 18 of 18 for “"Colored graphs"”.
-
Results on edge-colored graphs and pancyclicity
… with additional structure contains certain subgraphs, particularly circuits, cycles, or trees. The specific problems and presented results include a blend of many fundamental graph theory concepts such as edge-coloring, routing problems, decomposition problems, and containing cycles of various …
-
Rainbow paths and trees in properly-colored graphs
<p>A graph $G$ is \textit{properly $k$-colored} if the colors $\{1,2,\dots,k\}$ are assigned to each vertex such that $u$ and $v$ have different colors if $uv$ is an edge and each color is assigned to some vertex. A \textit{rainbow $k$-path}, a \textit{rainbow $k$-star} and a \textit{rainbow …
-
Sparse color-critical graphs and rainbow matchings in edge-colored graphs
Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2013-04-05T19:14:32Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 26 THESIS_04.tex: 303472 bytes, checksum: ac02fb44aef43edf6047cfd6a308c01b (MD5) Setup.pdf: 26974 bytes, checksum: …
-
On the Property F Conjecture
… is to translate the problem into manipulation of colored graphs embedded in the given surface as defined by Kirillov. To do this translation, we use the fact that any such representation associated to a finite group G and 3-cocycle ɯ is isomorphic to a Turaev-Viro-Barrett-Westbury (TVBW) …
-
Conceptual Design of Dual Cam Mechanisms Using Graph Theory
This paper presents the theory of graphs and how they can be applied to the conceptual design of dual-cam mechanisms. The graph theory was used to validate the results of previous authors (Hain and Pryor). Several applications of dual cam mechanisms are reviewed. Algorithms using a process of bit …
-
An integrated complexity analysis of problems from computational biology
… algorithmic design techniques for bounded width graphs, and parameterized computational complexity together provide a clear and detailed map of the intrinsic hardness of the following problems: INTERVALIZING COLORED GRAPHS and SHORTEST COMMON SUPERSEQUENCE. The fundamental concern of …
-
Conflict Free Connectivity and the Conflict-Free-Connection Number of Graphs
We explore a relatively new concept in edge-colored graphs called conflict-free connectivity. A conflict-free path is a (edge-) colored path that has an edge with a color that appears only once. Conflict-free connectivity is the maximal number of internally disjoint conflict-free paths between all …
-
Ramsey regions and simplicial homology tables for graphs
Ramsey Theory is the investigation of edge-colored graphs which force a monochromatic subgraph. We devise a way of breaking certain Ramsey Theory problems into "smaller" pieces so that information about Ramsey Theory can be gained without solving the entire problem, (which is often difficult to …
-
Symmetry Detection in Integer Linear Programs
… group of the graph. Unfortunately, these graphs may be much larger than the IP problem, resulting in a possible waste of computational resources. The approach of this thesis is to detect the group of an edge-colored graph generated by the IP. This avoids the need for additional nodes to …
-
Colored Saturation Parameters for Bipartite Graphs
Let F and H be fixed graphs and let G be a spanning subgraph of H. G is an F-free subgraph of H if F is not a subgraph of G. We say that G is an F-saturated subgraph of H if G is F-free and for any edge e in E(H)-E(G), F is a subgraph of G+e. The saturation number of F in K_{n,n}, denoted …
-
Combinatorial algorithms on partially ordered sets
… orderly algorithms for constructing acyclic digraphs, acyclic transitive digraphs, finite topologies and finite topologies and finite lattices. For the first time we show that the number of finite lattices on 11, 12, and 13 elements are 37622, 262775, and 2018442, respectively, and the number …
-
Bayesian Estimation of Graphical Gaussian Models with Edges and Vertices Symmetries
… as RCON models. The models can be represented by colored graphs, where edges or vertices have the same coloring if the corresponding elements of the precision matrix are equal. In this thesis, we define a conjugate prior distribution for RCON models. We will, therefore, call this conjugate prior …
-
Turán Problems and Spectral Theory on Hypergraphs and Tensors
Turán problems on uniform hypergraphs have been actively studied for many decades. However, on non-uniform hypergraphs, these problems are rarely considered. We refer a non-uniform hypergraph as an R-hypergraph where R is the set of cardinalities of all edges. An R-graph H is called degenerate if …
-
Advances in combined architecture, plant, and control design
… is addressed with methods developed based on colored graphs built by enumerating all perfect matchings of a specified catalog of components. The proposed approach captures all architectures under specific assumptions. General combined plant and control design (or co-design) problems are …
-
Successful Pressing Sequences in Simple Pseudo-Graphs
… “successful pressing sequences” in simple pseudo-graphs. Pressing sequences where first introduced by Hannenhali and Pevzner in 1999 where they showed that sorting signed permutation problem can be solved in polynomial time, therefore demonstrating that the length of a most parsimonious solution …
-
Attacks On Difficult Instances Of Graph Isomorphism: Sequential And Parallel Algorithms
… algorithms, for determining if a pair of graphs are isomorphic, are based on the individualization-refinement paradigm, pioneered by Brendan McKay in 1981 with his algorithm nauty. Nauty and various improved descendants of nauty, such as bliss and saucy, solve the graph isomorphism problem …
-
Graph-based Path Planning for Mobile Robots
… higher level of abstraction. Given is a weighted colored graph where vertices are assigned a color (or class) that indicates a feature or quality of the environment associated with that vertex. The question is then asked, ``what is the globally optimal path through this weighted colored graph?' We …
-
An Information-Theoretic Framework for Resource-Aware Abstraction and Planning for Autonomous Agents
… abstractions may be employed to create informed colored-graphs for semantic-planning.