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 26 for “"Maximum Clique Problem"”.

  1. The Maximum Clique Problem: Algorithms, Applications, and Implementations

    <p>Computationally hard problems are routinely encountered during the course of solving practical problems. This is commonly dealt with by settling for less than optimal solutions, through the use of heuristics or approximation algorithms. This dissertation examines the alternate possibility of …

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

  2. A Comparison of Quantum Algorithms for the Maximum Clique Problem

    … of superposition and entanglement to solve problems using qubits based on technologies ranging from magnetic fields created from superconducting materials to the spins of valence electrons in atoms. Boson sampling is a non-universal form of quantum computation that uses bosons as …

    rit Repository record for A Comparison of Quantum Algorithms for the Maximum Clique Problem (opens in a new tab)

  3. Analysis of Reactive Search Optimisation Techniques for the Maximum Clique Problem and Applications

    … current state of the art of heuristics for the Maximum Clique (MC) problem. The analysis focusses on algorithmic building blocks, on their contribution in solving hard instances of the MC problem, and on the development of new tools for the visualisation of search landscapes. As a result of the …

    trento Repository record for Analysis of Reactive Search Optimisation Techniques for the Maximum Clique Problem and Applications (opens in a new tab)

  4. Two topics in combinatorial optimization: the domino portrait problem and the maximum clique problem

    … supplying solutions to many scientific problems in a variety of fields, including computer science and computational networks. This dissertation first reviews a number of problems from combinatorial optimization and the algorithms used to solve them.

    colostate Repository record for Two topics in combinatorial optimization: the domino portrait problem and the maximum clique problem (opens in a new tab)

  5. Algorithms for Computing Edge-Connected Subgraphs

    … to develop a scale reduction procedure for the maximum clique problem. The proposed scale-reduction approach is based on the observation that a subset C of k + 1 vertices is a clique if and only if one needs to remove at least k edges in order to disconnect the corresponding induced subgraph …

    tamu Repository record for Algorithms for Computing Edge-Connected Subgraphs (opens in a new tab)

  6. Characterizing Structurally Cohesive Clusters in Networks: Theory and Algorithms

    … approaches for studying cluster detection problems that typically arise in networks. More specifically, we consider graph theoretic relaxations of clique as models for characterizing structurally cohesive and robust subgroups, developing strong upper bounds for the maximum clique problem, …

    tamu Repository record for Characterizing Structurally Cohesive Clusters in Networks: Theory and Algorithms (opens in a new tab)

  7. Parameterized Approaches for Large-Scale Optimization Problems

    … we study challenging discrete optimization problems from the perspective of parameterized complexity. The usefulness of this type of analysis is twofold. First, it can lead to efficient algorithms for large-scale problem instances. Second, the analysis can provide a rigorous explanation for …

    tamu Repository record for Parameterized Approaches for Large-Scale Optimization Problems (opens in a new tab)

  8. Solving the maximum clique problems on a class of network graphs, with applications to social networks

    … network analysis frequently uses the idea of a clique in a network to identify key subgroups of highly-connected members of the network. We formulate the maximum clique problem on undirected graphs and develop two algorithms to solve it: a pruning algorithm and an enumeration algorithm. The …

    nps Repository record for Solving the maximum clique problems on a class of network graphs, with applications to social networks (opens in a new tab)

  9. Graph theoretic generalizations of clique: optimization and extensions

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

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

  10. A parallel workflow for online correlation and clique-finding : with applications to finance

    … Stochastic Local Search (SLS) algorithm for the maximum clique problem can be adapted for and employed within a fully distributed parallel workfiow environment. First we present parallel variants of Dynamic Local Search (DLS-MC) and Phased Local Search (PLS), demonstrating how a simple yet …

    ubc Repository record for A parallel workflow for online correlation and clique-finding : with applications to finance (opens in a new tab) Download PDF for A parallel workflow for online correlation and clique-finding : with applications to finance (opens in a new tab)

  11. Planar maximal covering location problem under different block norms

    … model for the planar maximal covering location problem (PMCLP) under different block norms. The problem involves locating p facilities anywhere on the plane in order to cover the maximum number of n given demand points. The generalization we introduce is that distance measures assigned to …

    mcmaster Repository record for Planar maximal covering location problem under different block norms (opens in a new tab)

  12. Higher-Order Continuous Formulations For Discrete Optimization Problems

    … programming formulations for a class of problems related to community detection in networks. The proposed approach is based on the extension of quadratic formulations that were proposed by Motzkin and Strauss in 1967. These formulations are related to the Maximum Clique problem, which …

    tamu Repository record for Higher-Order Continuous Formulations For Discrete Optimization Problems (opens in a new tab)

  13. Scalable Parallel Branch-and-Bound with Relaxed Concurrent Queues - A Study of Relaxed Concurrent Queues in Branch-and-Bound using a Generic Solver Framework

    … solving is developed. The framework separates problem-specific logic from parallel execution and queue management, greatly simplifying the development of high-performing branch-and-bound solvers. The framework is evaluated primarily through a case study on the Maximum Clique Problem using …

    chalmers Repository record for Scalable Parallel Branch-and-Bound with Relaxed Concurrent Queues - A Study of Relaxed Concurrent Queues in Branch-and-Bound using a Generic Solver Framework (opens in a new tab)

  14. Convex relaxation for the planted clique, biclique, and clustering problems

    A clique of a graph G is a set of pairwise adjacent nodes of G. Similarly, a biclique (U, V ) of a bipartite graph G is a pair of disjoint, independent vertex sets such that each node in U is adjacent to every node in V in G. We consider the problems of identifying the maximum clique of a graph, …

    waterloo Repository record for Convex relaxation for the planted clique, biclique, and clustering problems (opens in a new tab)

  15. Maximum Clique in Geometric Intersection Graphs

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

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

  16. Clique Relaxations & the Minority Districting Problem

    … through three combinatorial optimization problems. We model each problem on graphs and exploit the inherent structure of the problem to propose novel integer programming formulations, create fixing procedures, and add valid cuts to the problem. We demonstrate the theoretical and …

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

  17. Methodologies for predicting and explaining the empirical hardness of graph-based combinatorial optimization problems

    … association rule mining (ARM). Applied to 3,287 maximum clique problem (MCP) instances drawn from COLLAB, IMDB-BINARY, and TWITTER benchmarks, the framework achieves a weighted F1 ≈0.992 using features: two adjacency matrix-based spectral statistics and the number of nodes. It then extracts …

    mcmaster Repository record for Methodologies for predicting and explaining the empirical hardness of graph-based combinatorial optimization problems (opens in a new tab)

  18. Scalable Scientific Computing Algorithms Using MapReduce

    … computational tasks, while a large class of problems in scientific computing and business analytics are computationally intensive (i.e., they require a lot of CPU in addition to I/O). In this thesis, we investigate the use of cloud computing systems, in particular MapReduce, for …

    waterloo Repository record for Scalable Scientific Computing Algorithms Using MapReduce (opens in a new tab)

  19. Novel approaches for solving large-scale optimization problems on graphs

    … a class of closely related NP-hard otpimization problems on graphs that arise in many important applications, including network-based data mining, analysis of the stock market, social networks, coding theory, fault diagnosis, molecular biology, biochemistry and genomics. In particular, the …

    tamu Repository record for Novel approaches for solving large-scale optimization problems on graphs (opens in a new tab)

Page 1 of 2