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"”.
-
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 …
-
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, …
-
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 …
-
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.
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
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, …
-
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 …
-
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 …
-
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), …
-
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: …
-
Προσεγγιστικά σχήματα, κλίκες, χρώματα και πυκνότεροι υπογράφοι
… 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 …
-
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 …
Page 1 of 3