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 427 for “"Clique"”.
-
Coloring clique hypergraphs
Let G = (V, E) be a simple graph. The clique hypergraph of G, denoted as CH( G), has V as its set of vertices, and the maximal cliques as its hyperedges. Let Sk be a set of k colors. A map c : V Sk is a proper k-coloring for CH(G) if any maximal clique of G with at least two vertices receives at …
-
Clique minors in dense matroids
The objective of this thesis is to bound the number of points a $U_{2,\ell+2}$- and $M(K_{k+1})$-minor-free matroid has. We first prove that a sufficiently large matroid will contain a structure called a tower. We then use towers to find a complete minor in a matroid with no $U_{2,\ell+2}$-minor.
-
Clique Generalizations and Related Problems
… 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 modeling …
-
Clique graph models for independent computations
… structural interrelationships clearly is the clique graph. Clique graphs are used in the development of divide-and-conquer algorithms, sparse matrix factorization schemes, and information propagation in knowledge-based systems, among other important applications.</p> <p>This dissertation …
-
Maximum Clique in Geometric Intersection Graphs
… to the items that intersect. The maximum clique in a geometric intersec- tion graph is the largest mutually intersecting set of objects. In this thesis, the primary focus is to study the maximum clique in various geometric intersection graphs. We develop three results motivated by the …
-
Minimal Classes of Unbounded Clique-Width
In the study of graphs, clique-width is a parameter that has received much attention due its significance in the tractability of algorithms on certain classes of graph. Of particular interest are hereditary graph classes, those classes closed under taking induced subgraphs. A number of <i>minimal …
-
Clique Relaxations & the Minority Districting Problem
… problem, which itself is a relaxation of a clique. We propose an integer programming formulation for the anchored k-core problem, define and study the polyhedra of the maximum anchored k-core problem, and provide a computational study comparing our model against leading algorithms in the …
-
Bilevel Clique Interdiction and Related Problems
I introduce a formulation of the bilevel clique interdiction problem. Interdiction, a military term, describes the removal of enemy resources. The single level clique interdiction problem describes the attempt of an attacker to interdict a maximum number of cliques. The bilevel form of the problem …
-
Clique Factors: Extremal and Probabilistic Perspectives
A K_r-factor in a graph G is a collection of vertex-disjoint copies of K_r covering the vertex set of G. In this thesis, we investigate these fundamental objects in three settings that lie at the intersection of extremal and probabilistic combinatorics. Firstly, we explore pseudorandom graphs. An …
-
Maximum Clique Search in Circulant k-Hypergraphs
The search for max-cliques in graphs is a well established NP-complete problem in graph theory and algorithm design, with many algorithms designed to make use of internal structures of specific types of graphs. We study the extension of the problem of searching for max-cliques in graphs to …
-
The Maximum Clique Problem: Algorithms, Applications, and Implementations
… study of one particular problem, the maximum clique problem. It discusses algorithms, implementations, and the application of maximum clique results to real-world problems. First, the theoretical roots of the algorithmic method employed are discussed. Then a practical approach is described, …
-
On the efficiency of clique detection in graphs
… complete subgraphs in graphs. Also known as cliques, in Chapter 1 these subgraphs are seen to play an important role in graph theory, information retrieval, Sociometry, logic design, and computational complexity. The enumeration of cliques using the Harary-Rcss, Bonner, Peay, and …
-
A clique tree algorithm exploiting context specific independence
… that exploits context specific independence in clique tree propagation. This algorithm is based on a query-based contextual variable elimination algorithm (eve) that eliminates in turn the variables not needed in an answer. We extend eve to producing the posterior probabilities of all variables …
-
Sparsity in Critical Graphs with Small Clique Number
… value of $\varepsilon$ is the case of small clique number. We derive new density lemmas exploiting this case by showing that our graph is contained in a complete multipartite graph with many parts of size three. In order to list colour in this setting, we apply a theorem of Noel, West, Wu and …
-
Graph theoretic generalizations of clique: optimization and extensions
… graph theoretic generalizations of the maximum clique problem. Models that were originally proposed in social network analysis literature, are investigated from a mathematical programming perspective for the first time. A social network is usually represented by a graph, and cliques were the …
-
Mathematical Foundations and Algorithms for Clique Relaxations in Networks
… the properties exhibited by generalizations of cliques, as well as algorithms to find such objects in a network. Cliques are a model of an ideal group with roots in social network analysis. They have since found applications as a part of grouping mechanisms in computer vision, coding theory, …
-
Covering arrays avoiding forbidden edges and edge clique covers
… CAFEs, as well as their relationship to the edge clique cover problem from graph theory. We give new results and bounds for uniform edge clique covers and CAFEs. We establish the computational complexity of several problems related to CAFEs and edge clique covers. In particular, we prove that …
-
Maximal Clique Enumeration and Related Tools for Microarray Data Analysis
… was to investigate the utility of exact maximal clique enumeration in DNA microarray analysis, to analyze and improve upon existing exact maximal clique enumeration algorithms, and to develop new clique-based algorithms to assist in the analysis as indicated during the course of the study. As a …
Page 1 of 22