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 47 for “"Chordal Graphs"”.

  1. Practical parallel algorithms for chordal graphs

    <p>Given a chordal graph, parallel solutions are given for finding the set of maximal cliques, a perfect elimination ordering and a minimum coloring. The solutions to these problems have a variety of applications. While other parallel solutions to these problems exist, this paper presents …

    ut-knoxville Repository record for Practical parallel algorithms for chordal graphs (opens in a new tab)

  2. Succinct Data Structures for Chordal Graphs

    … problem of approximate shortest path queries in chordal graphs and give a n log n + o(n log n) bit data structure to answer the approximate distance query to within an additive constant of 1 in O(1) time. We study the problem of succinctly storing a static chordal graph to answer adjacency, …

    waterloo Repository record for Succinct Data Structures for Chordal Graphs (opens in a new tab)

  3. Edge completion sequences for classes of chordal graphs

    Given an incomplete graph G = (V, E) of order n and size m and possessing some property P, a P-Completion sequence for G is a sequence e1,,,,,,es of edges, where s = (n2) - m, with the property that if Go = G then (1) Gi is obtaIned from G(i-1) by insertion of exactly one edge and (2) Gi has …

    nps Repository record for Edge completion sequences for classes of chordal graphs (opens in a new tab)

  4. Edge annihilation sequences for classes of chordal graphs

    … P, we may ask whether there exists a sequence of graphs constructed by the sequential removal of edges e1, e2,...,em, with the property that if Go=G then (1) Gi is obtained from G(i-1) by deletion of exactly one edge and (2) Gi has property P for 1.

    nps Repository record for Edge annihilation sequences for classes of chordal graphs (opens in a new tab)

  5. Efficient Sampling and Counting of Graph Structures related to Chordal Graphs

    … of graph structures on different types of graphs have been studied for decades for their great importance in areas like complexity theory and statistical physics. For many graph structures such as independent sets and acyclic orientations, it is widely believed that no exact or approximate …

    rit Repository record for Efficient Sampling and Counting of Graph Structures related to Chordal Graphs (opens in a new tab)

  6. On chordal digraphs and semi-strict chordal digraphs

    Chordal graphs are an important class of perfect graphs. The beautiful theory surrounding their study varies from natural applications to elegant characterizations in terms of forbidden subgraphs, subtree representations, vertex orderings, and to linear time recognition algorithms. Haskins and Rose …

    uvic Repository record for On chordal digraphs and semi-strict chordal digraphs (opens in a new tab)

  7. Biclique Partitions, Biclique Covers, and Disjunctive Constraints

    … partition and biclique cover problems on co-chordal graphs, which is the complementary graph of chordal. We provide heuristics to find biclique partitions on co-chordal graphs and show that the heuristics can provide biclique partitions close to optimal or even optimal if the graphs satisfy …

    rice Repository record for Biclique Partitions, Biclique Covers, and Disjunctive Constraints (opens in a new tab)

  8. Building a larger class of graphs for efficient reconfiguration of vertex colouring

    … It is known that not all weakly chordal graphs have the property that $\mathcal{R}_{k+1}(G)$ is connected. On the other hand, $\mathcal{R}_{k+1}(G)$ is connected and of diameter $O(n^2)$ for several subclasses of weakly chordal graphs such as chordal, chordal bipartite, and …

    waterloo Repository record for Building a larger class of graphs for efficient reconfiguration of vertex colouring (opens in a new tab)

  9. A chordal sparsity approach to scalable linear and nonlinear systems analysis

    … this thesis we investigate how the properties of chordal graphs can be used to exploit sparsity in several optimisation problems that arise in control theory. In particular, we focus on analysis and synthesis problems that involve semidefinite constraints and can be formulated as semidefinite …

    oxford Repository record for A chordal sparsity approach to scalable linear and nonlinear systems analysis (opens in a new tab)

  10. Induced-minor-closed classes of matroids

    A graph is chordal if every cycle of length at least four has a chord. In 1961, Dirac characterized chordal graphs as those graphs that can be built from complete graphs by repeated clique-sums. Generalizing this, we consider the class of simple GF(q)-representable matroids that can be built from …

    lsu-thes Repository record for Induced-minor-closed classes of matroids (opens in a new tab)

  11. Homomorphisms of Graphs

    Understanding the structure of graphs is fundamental to advances in many areas of graph theory, as well as in many applications. In many cases, an analysis of the structure of graphs follows one of two approaches; either many structural properties are considered over a restricted class of graphs, …

    clemson Repository record for Homomorphisms of Graphs (opens in a new tab)

  12. Chordality of digraphs, signed graphs, and signed bigraphs

    Chordal graphs and chordal bigraphs enjoy beautiful characterizations, in terms of forbidden subgraphs, vertex or edge orderings, and tree-like representations. A digraph analogue of chordal graphs was introduced by Haskins and Rose. Unfortunately, a forbidden subdigraph characterization of chordal …

    uvic Repository record for Chordality of digraphs, signed graphs, and signed bigraphs (opens in a new tab)

  13. A New Optimality Measure for Distance Dominating Sets

    … even when the input graph is restricted to split graphs, <em>2</em>-connected graphs, or planar bipartite graphs of degree four. In addition, the problem is in P for bounded tree-width graphs, when considering <em>k</em> as a constant, and for strongly chordal graphs, for any <em>k</em>. Then, we …

    waterloo Repository record for A New Optimality Measure for Distance Dominating Sets (opens in a new tab)

  14. Broadcast independence and broadcast packing

    … two broadcast parameters in different classes of graphs. Determining the broadcast independence number is NP-hard for planar graphs of maximum degree 4, and before this thesis, the best known algorithm to compute the broadcast independence number of a tree of order n had time complexity O(n^9), …

    uvic Repository record for Broadcast independence and broadcast packing (opens in a new tab)

  15. Algorithms and complexity of graph modification problems

    … was recently shown to be NP-complete for general graphs. Here we initiate the study of graph classes for which MaxSTC is solvable in polynomial time or NP-complete. On the positive side, we show that the problem admits a polynomial-time algorithm for the following incomparable classes of graphs: …

    greece Repository record for Algorithms and complexity of graph modification problems (opens in a new tab)

  16. Προσεγγιστικά σχήματα, κλίκες, χρώματα και πυκνότεροι υπογράφοι

    … for the densest k-subgraph problem on weighted graphs of maximal degree two, on weighted trees even if the solution is disconnected, and on interval graphs with intersection only between two consecutive cliques. Moreover, we present a polynomial time approximation scheme for the densest …

    greece Repository record for Προσεγγιστικά σχήματα, κλίκες, χρώματα και πυκνότεροι υπογράφοι (opens in a new tab)

  17. Completion of partial operator matrices

    … linear operators between Hilbert spaces). Graphs are associated with partial matrices. Chordal graphs and directed graphs with a perfect edge elimination scheme play a key role in our considerations. A specific choice for the unspecified entries is referred to as a completion of the partial …

    wm-mary Repository record for Completion of partial operator matrices (opens in a new tab)

Page 1 of 3