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 4 of 4 for “"Max-Clique"”.

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

    ubc Repository record for On uniform sampling of cliques (opens in a new tab) Download PDF for On uniform sampling of cliques (opens in a new tab)

  2. A parametric classification of directed acyclic graphs

    … on directed acyclic graphs (DAGs), namely, max clique, min coloring, max independent set and min clique cover. It is well-known that these four problems can be solved in polynomial time on transitive DAGs. It is also known that there can be no polynomial O(n1-ϵ)-approximation algorithms for …

    colostate Repository record for A parametric classification of directed acyclic graphs (opens in a new tab)

  3. Intractability Results for some Computational Problems

    … output any efficiently computable hypothesis. Max-Clique, Chromatic Number and Min-3Lin-Deletion: We prove an improved hardness of approximation result for two problems, namely, the problem of finding the size of the largest clique in a graph (also referred to as the Max-Clique problem) and the …

    gatech Repository record for Intractability Results for some Computational Problems (opens in a new tab)

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