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"”.

  1. 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 …

    rice Repository record for The Closure of the Minimal k-core Problem for Modeling k-assemblies (opens in a new tab)

  2. 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 …

    colostate Repository record for Modular decomposition of undirected graphs (opens in a new tab)

  3. 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 …

    tamu Repository record for Critical Cliques and Their Application to Influence Maximization in Online Social Networks (opens in a new tab)

  4. 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 …

    waterloo Repository record for Matrix Formulations of Matching Problems (opens in a new tab)

  5. Generalizations of the Zero-Divisor Graph of a Ring

    … the set of zero­divisors 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 …

    utk-theses Repository record for Generalizations of the Zero-Divisor Graph of a Ring (opens in a new tab)

  6. 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 …

    clemson Repository record for Domination in Graphs and the Removal of a Matching (opens in a new tab)

  7. 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 …

    waterloo Repository record for Minimum Crossing Problems on Graphs (opens in a new tab)

  8. 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 …

    sask Repository record for A general computational tool for structure synthesis (opens in a new tab)

  9. 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 …

    byu Repository record for Properties of the Zero Forcing Number (opens in a new tab) Download PDF for Properties of the Zero Forcing Number (opens in a new tab)

  10. 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 …

    carleton Repository record for On Two Problems Regarding Farthest Distances in Continuous Networks (opens in a new tab)

  11. 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 …

    nps Repository record for Locating absolute 2-centers of undirected graphs (opens in a new tab)

  12. 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 …

    must-thes Repository record for Graph coloring algorithms on random graphs (opens in a new tab)

  13. 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 …

    ubc Repository record for Link scheduling directed graphs using undirected edge colours (opens in a new tab) Download PDF for Link scheduling directed graphs using undirected edge colours (opens in a new tab)

  14. 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 …

    jhu Repository record for Interval Digraphs (opens in a new tab)

  15. 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 …

    uvic Repository record for Probabilistic graph colouring algorithms using Zykov trees (opens in a new tab)

  16. 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 …

    wvu Repository record for Topics in Graph Compositions (opens in a new tab)

  17. 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 …

    wvu Repository record for On the Design, Analysis, and Implementation of Algorithms for Selected Problems in Graphs and Networks (opens in a new tab)

  18. 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 …

    rice Repository record for Clique Generalizations and Related Problems (opens in a new tab)

  19. 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 …

    aalto Repository record for Interactions of Algebra, Statistics and Optimization (opens in a new tab)

  20. 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 …

    texas-state Repository record for Parallel Implementation of a Minimum Spanning Tree Algorithm (opens in a new tab)

Page 1 of 7