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 272 for “"Cliques"”.
-
Cliques, colours and clusters
In this thesis, we derive several results concerning extremal graph theory and probability theory, focusing particularly on proper colourings of graphs. First, we prove a special case of the Bollobás-Eldridge-Catlin conjecture, for graphs of bounded codegree. This implies an upperbound on the …
-
On uniform sampling of cliques
… thesis is the problem of sampling uniformly the cliques of a target size k of any given graph. As a natural approach for solving this problem, we used the already available state-of-the-art heuristic MAX-CLIQUE solvers. The heuristic MAX-CLIQUE algorithms, which we used for this task, have …
-
Displaying cliques in graph drawings
… identifying useful information, such as maximal cliques, in the graph. This thesis attempts to display the maximal cliques and the cliques contained in two or more maximal cliques in a given graph in an explicit and clear fashion. In order to achieve the goal, the thesis defines two models, the …
-
Cycles and Cliques in Steinhaus Graphs
… to enumerate the Steinhaus graphs having maximal cliques. Finally the concept of jumbled graphs and Posa's Lemma are used to show that almost all Steinhaus graphs are Hamiltonian.
-
Exploring Collegiate Athletes' Experiences with Cliques
… smaller units present within a team, such as cliques or subgroups, warrant further scientific exploration and dissemination (Wagstaff & Martin, 2018). Existent literature on cliques in an athletic setting established that intra-team groups are inevitable, while also highlighting their …
-
Broadcasting in graphs containing intersecting cliques
… various graph topologies containing intersecting cliques. Broadcasting, is a fundamental message dissemination problem in interconnection networks, requiring an informed originator node to distribute information to all network nodes efficiently. Determination of the broadcast time of any node in …
-
Counting cliques in graphs with excluded minors
… minors, focusing on the maximum number of k-cliques such graphs can contain. The first part of the thesis studies planar graphs, which forbid K5 and K3,3 as minors. We determine the maximum number of edges is in a planar graph that contains no cycle of length k, and establish a general upper …
-
Chromatic Thresholds of Regular Graphs with Small Cliques
… this method to graphs that are free of larger cliques in order to limit the possible values of the chromatic threshold for regular <em>Kr</em>-free graphs.</p>
-
On Fork-Join Queues and Maximum Ratio Cliques
… of benefit and cost weights associated with the cliques vertices. This problem is formulated to model networks in which the vertices have a benefit as well as a cost associated with them. The maximum ratio clique problem finds applications in a wide range of areas including social networks, stock …
-
Mining maximal cliques from large graphs using MapReduce
… <em>PECO</em> (Parallel Enumeration of Cliques using Ordering); a novel parallel MCE algorithm. Unlike previous works, which require a post-processing step to remove duplicate and non-maximal cliques, <em>PECO</em> enumerates maximal cliques with no duplicates while minimizing work …
-
Cliques in block graphs of designs and orthogonal arrays
The Erdos-Ko-Rado [EKR] Theorem for intersecting families is a fundamental result in combinatorics, particularly in extremal set theory. This theorem not only establishes an upper bound on the size of the largest intersecting family but also characterizes the families that attain this bound—–these …
-
Lossless Coding of Markov Random Fields with Complex Cliques
… cases of the BP algorithm: MRFs with only simple cliques, and MRFs with complex cliques. In the latter case, we study a minimum radius condition requirement for ensuring that all cliques are accounted for during coding. This condition also simplifies the process of conditioning on observed sites. …
-
Cliques, Degrees, and Coloring: Expanding the ω, Δ, χ paradigm
… on the density of critical graphs without large cliques, a long-standing problem, answering a question of Kostochka and Yancey. In the proof, we use a novel application of the discharging method to find a set of vertices for which any precoloring can be extended to the remainder of the graph …
-
Enumerating K-Cliques in a Large Network Using Apache Spark
… over a large network. However, enumerating cliques using sequential technologies is very time-consuming. Another promising direction that is being adopted is a solution that runs on distributed clusters of machines using the Hadoop mapreduce framework. However, the solution suffers from a …
-
The Complexity of Finding Dense Subgraphs in Graphs with Large Cliques
The GapDensest-k-Subgraph(d) problem (GapDkS(d)) is defined as follows: given a graph G and parameters k,d, distinguish between the case that G contains a k-clique, and the case that every k-subgraph of G has density at most d. GapDkS(d) is a natural relaxation of the standard Clique problem, which …
-
Approximating 4-cliques in streaming graphs: the power of dual sampling
… are known for estimating clique counts, 4-cliques have not received as much attention as triangles in the streaming setting. In this work, we propose 4CDS, a fast and scalable algorithm for approximating 4-clique counts in a single-pass streaming model. By leveraging a combination of …
-
Critical Cliques and Their Application to Influence Maximization in Online Social Networks
… Series modules which are maximal and are also cliques are termed as simple series modules or critical cliques. There are modular decomposition algorithms that can be used to decompose the graph into modules and obtain critical cliques. In this current research, we present a new algorithm to …
Page 1 of 14