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 51 for “"maximum clique"”.
-
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 …
-
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
… a detailed 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 …
-
A Comparison of Quantum Algorithms for the Maximum Clique Problem
… solving the given problem. This thesis uses the maximum clique problem to examine the application development process in the qubit gate model and boson sampling as well as a comparison of other known algorithms to the maximum clique problem. The maximum clique problem is an NP-Hard problem …
-
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 …
-
Two topics in combinatorial optimization: the domino portrait problem and the maximum clique problem
Combinatorial Optimization plays a significant role in applied mathematics, 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 …
-
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 …
-
Cycles and Cliques in Steinhaus Graphs
… graphs is at most [(n+3)/2]. Next the results of maximum clique size in Steinhaus graphs are used 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.
-
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 …
-
Scalable Scientific Computing Algorithms Using MapReduce
… in scienti c computing and also in analytics: maximum clique and matrix inversion. The key contribution that enables us to e ectively use MapReduce to solve the maximum clique problem on dense graphs is a recursive partitioning method that partitions the graph into several subgraphs of similar …
-
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 …
-
Characterizing Structurally Cohesive Clusters in Networks: Theory and Algorithms
… 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, and present a new relaxation that is useful in clustering applications. We consider the clique relaxation …
-
Parameterized Approaches for Large-Scale Optimization Problems
… on several different problems, including: the maximum clique problem in sparse graphs; 0-1 programs with many conflicts; and the node-weighted Steiner tree problem with few terminal nodes. We also study polyhedral counterparts to fixed-parameter tractable algorithms. Specifically, we provide …
-
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, …
-
Generalised disk graphs
… two dimensions and give exact solutions to the maximum weighted independent set and maximum clique problems in one dimension.
-
THEORY AND ALGORITHMS FOR COMMUNITY DETECTION AND CLUSTERING IN NETWORKS
… We present a comprehensive study of the maximum independent union of cliques problem and its generalizations in uniform random graphs. The main result is the logarithmic upper bound, similarly to the maximum clique, which suggests a subexponential algorithm. Then we propose a parallel …
-
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 …
-
On hereditary graph classes defined by forbidding Truemper configurations: recognition and combinatorial optimization algorithms, and χ-boundedness results
… results to analyze the complexity of the maximum clique, maximum stable set and optimal coloring problems restricted to these classes. Finally, we provide polynomial-time recognition algorithms for all of these classes, and we obtain χ-boundedness results.
Page 1 of 3