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 123 for “"undirected graph"”.
-
The Closure of the Minimal k-core Problem for Modeling k-assemblies
… algorithm to find all minimal k-cores of a given undirected graph, which belongs to the class of NP-hard problems. The proposed method is a modification of the Bron and Kerbosch algorithm for finding all cliques of an undirected graph. The minimal k-core problem has applications in the area of …
-
Modular decomposition of undirected graphs
Graphs found in nature tend to have structure and interesting compositions that allow for compression of the information and thoughtful analysis of the relationships between vertices. Modular decomposition has been studied since 1967 [1]. Modular decomposition breaks a graph down into smaller …
-
Critical Cliques and Their Application to Influence Maximization in Online Social Networks
Graph decompositions have useful applications in optimization problems that are categorized as NP-Hard. Modular Decomposition of a graph is a technique to decompose the graph into non-overlapping modules. A module M of an undirected graph G = (V, E) is commonly defined as a set of vertices such …
-
Matrix Formulations of Matching Problems
Finding the maximum size of a matching in an undirected graph and finding the maximum size of branching in a directed graph can be formulated as matrix rank problems. The Tutte matrix, introduced by Tutte as a representation of an undirected graph, has rank equal to the maximum number of vertices …
-
Generalizations of the Zero-Divisor Graph of a Ring
… the set of zerodivisors of R. We define an undirected graph Γ(<em>R</em>) with vertices <em>Z</em>(<em>R</em>)* = <em>Z</em>(<em>R</em>) - {0}, where distinct vertices <em>x</em> and <em>y</em> of R are connected if and only if <em>xy</em> = 0. This graph is called the zero-divisor graph of …
-
Domination in Graphs and the Removal of a Matching
We consider how the domination number of an undirected graph changes on the removal of a maximal matching. It is straightforward that there are graphs where no matching removal increases the domination number, and where some matching removal doubles the domination number. We show that in a …
-
Minimum Crossing Problems on Graphs
… biology and computer science. Given an undirected graph G=(V,E) and a family of subsets of vertices S, the minimum crossing spanning tree is a spanning tree where the maximum number of edges crossing any single set in S is minimized, where an edge crosses a set if it has exactly one …
-
A general computational tool for structure synthesis
… concepts: (1) the structure is represented by a graph and further by the adjacency matrix; and (2) instead of only exploiting the eigenvalue of the adjacency matrix, both the eigenvalue and the eigenvector are exploited; specifically the components of the eigenvector have been found very useful …
-
Properties of the Zero Forcing Number
The zero forcing number is a graph parameter first introduced as a tool for solving the minimum rank problem, which is: Given a simple, undirected graph G, and a field F, let S(F,G) denote the set of all symmetric matrices A=[a_{ij}] with entries in F such that a_{ij} doess not equal 0 if and only …
-
On Two Problems Regarding Farthest Distances in Continuous Networks
… along the edges of a network, i.e., a connected, undirected graph with positive edge weights. We measure the distance between these points in terms of the network distance, i.e., the weighted shortest path distance. The continuous diameter of a network is the largest network distance between any …
-
Locating absolute 2-centers of undirected graphs
… location of vertex and absolute 2-centers of an undirected graph. Under certain assumptions, these locations would be useful for determining the optimal positioning of emergency facilities such as fire stations. Vertex and absolute multi-centers are defined, and a procedure for locating the …
-
Graph coloring algorithms on random graphs
"The graph coloring problem, which is to color the vertices of a simple undirected graph with the minimum number of colors such that no adjacent vertices are assigned the same color, arises in a variety of scheduling problems. This dissertation focuses attention on vertex sequential coloring. Two …
-
Link scheduling directed graphs using undirected edge colours
… is typically modeled as either a directed or an undirected communication graph. Link scheduling is the problem of assigning time slots to each edge so that communication on every edge at its assigned time may occur without interference. Interference is also modeled as a graph, typically the same …
-
Interval Digraphs
We say that a simple, undirected graph interval graph if there exists a function mapping the vertices of the graph to intervals such that each pair of vertices is adjacent if and only if the corresponding intervals have a non-empty intersection. Undirected interval graphs were originally of …
-
Probabilistic graph colouring algorithms using Zykov trees
Let G=(V ,E) be a simple, undirected graph. A colouring of G is a mapping c : V ➔ {1,2, ... ,k}. c is a proper colouring if c(u) * c(v) for all {u,v} in E. The chromatic number of G, denoted x (G), is the smallest positive integer k for which a proper k-colouring exists. The graph colouring …
-
Topics in Graph Compositions
For any discrete undirected graph G with vertex set V(G) and edge set E(G) (respectively), a graph composition of G is defined to be a partition of V(G) where every element of the partition yields a connected, induced subgraph of G. This dissertation is comprised of 5 chapters. The first is a …
-
On the Design, Analysis, and Implementation of Algorithms for Selected Problems in Graphs and Networks
… spanning tree verification (MSTV) problem, the undirected negative cost cycle detection (UNCCD) problem, and the negative cost girth (NCG) problem. These problems find applications in several domains including program verification, proof theory, real-time scheduling, social networking, and …
-
Clique Generalizations and Related Problems
… can be model as optimization problems in graphs. The clique model was introduced to aid the study of network structure for social interaction. Each vertex represented an actor and the edges represented the relations between them. Nevertheless, the model has been shown to be restrictive for …
-
Interactions of Algebra, Statistics and Optimization
… satisfy certain dependence relations induced by graphs with undirected, directed and bidirected edges. We develop a package GraphicalModelsMLE for the computer algebra system Macaulay2 and discuss interesting applications to enable further research in this field. In Publication III, we take the …
-
Parallel Implementation of a Minimum Spanning Tree Algorithm
… a Minimum Spanning Tree (MST) of a weighted undirected graph is an important step in various applications, including circuit design, and it is desirable to build the MST quickly. However, current well-known approaches for building MSTs are not highly parallel. In this thesis, I propose a new …
Page 1 of 7