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

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

    wvu Repository record for Coloring clique hypergraphs (opens in a new tab)

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

    waterloo Repository record for Clique minors in dense matroids (opens in a new tab)

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

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

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

    utk-theses Repository record for Clique graph models for independent computations (opens in a new tab)

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

    sask Repository record for Maximum Clique in Geometric Intersection Graphs (opens in a new tab)

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

    the-open-u Download PDF for Minimal Classes of Unbounded Clique-Width (opens in a new tab)

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

    rice Repository record for Clique Relaxations & the Minority Districting Problem (opens in a new tab)

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

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

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

    fu-berlin Repository record for Clique Factors: Extremal and Probabilistic Perspectives (opens in a new tab)

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

    ottawa-retro Repository record for Maximum Clique Search in Circulant k-Hypergraphs (opens in a new tab)

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

    utk-theses Repository record for The Maximum Clique Problem: Algorithms, Applications, and Implementations (opens in a new tab)

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

    ubc Repository record for On the efficiency of clique detection in graphs (opens in a new tab) Download PDF for On the efficiency of clique detection in graphs (opens in a new tab)

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

    ubc Repository record for A clique tree algorithm exploiting context specific independence (opens in a new tab) Download PDF for A clique tree algorithm exploiting context specific independence (opens in a new tab)

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

    waterloo Repository record for Sparsity in Critical Graphs with Small Clique Number (opens in a new tab)

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

    tamu Repository record for Graph theoretic generalizations of clique: optimization and extensions (opens in a new tab)

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

    tamu Repository record for Mathematical Foundations and Algorithms for Clique Relaxations in Networks (opens in a new tab)

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

    ottawa-retro Repository record for Covering arrays avoiding forbidden edges and edge clique covers (opens in a new tab)

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

    ut-knoxville Repository record for Maximal Clique Enumeration and Related Tools for Microarray Data Analysis (opens in a new tab)

Page 1 of 22