ID: cs/0601117

Finding Cliques of a Graph using Prime Numbers

January 27, 2006

View on ArXiv

Similar papers 3

Poising on Ariadne's thread: An algorithm for computing a maximum clique in polynomial time

August 14, 2020

86% Match
Ioannis Avramopoulos
Computer Science and Game Th...
Computational Complexity

In this paper, we present a polynomial-time algorithm for the maximum clique problem, which implies P = NP. Our algorithm is based on a continuous game-theoretic representation of this problem and at its heart lies a discrete-time dynamical system. The rule of our dynamical system depends on a parameter such that if this parameter is equal to the maximum-clique size, the iterates of our dynamical system are guaranteed to converge to a maximum clique.

Find SimilarView on arXiv

Proof of Concept: Fast Solutions to NP-problems by Using SAT and Integer Programming Solvers

November 24, 2010

86% Match
Rastislav Lenhardt
Data Structures and Algorith...
Computational Complexity

In the last decade, the power of the state-of-the-art SAT and Integer Programming solvers has dramatically increased. They implement many new techniques and heuristics and since any NP problem can be converted to SAT or ILP instance, we could take advantage of these techniques in general by converting the instance of NP problem to SAT formula or Integer program. A problem we consider, in this proof of concept, is finding a largest clique in a graph. We ran several experiments...

Find SimilarView on arXiv

Shared-Memory Parallel Maximal Clique Enumeration

July 25, 2018

85% Match
Apurba Das, Seyed-Vahid Sanei-Mehri, Srikanta Tirthapura
Data Structures and Algorith...

We present shared-memory parallel methods for Maximal Clique Enumeration (MCE) from a graph. MCE is a fundamental and well-studied graph analytics task, and is a widely used primitive for identifying dense structures in a graph. Due to its computationally intensive nature, parallel methods are imperative for dealing with large graphs. However, surprisingly, there do not yet exist scalable and parallel methods for MCE on a shared-memory parallel machine. In this work, we prese...

Find SimilarView on arXiv

Shared-Memory Parallel Maximal Clique Enumeration from Static and Dynamic Graphs

January 30, 2020

85% Match
Apurba Das, Seyed-Vahid Sanei-Mehri, Srikanta Tirthapura
Distributed, Parallel, and C...

Maximal Clique Enumeration (MCE) is a fundamental graph mining problem, and is useful as a primitive in identifying dense structures in a graph. Due to the high computational cost of MCE, parallel methods are imperative for dealing with large graphs. We present shared-memory parallel algorithms for MCE, with the following properties: (1) the parallel algorithms are provably work-efficient relative to a state-of-the-art sequential algorithm (2) the algorithms have a provably s...

Find SimilarView on arXiv

Mining Maximal Cliques from an Uncertain Graph

October 24, 2013

85% Match
Arko Provo Mukherjee, Pan Xu, Srikanta Tirthapura
Data Structures and Algorith...
Databases

We consider mining dense substructures (maximal cliques) from an uncertain graph, which is a probability distribution on a set of deterministic graphs. For parameter 0 < {\alpha} < 1, we present a precise definition of an {\alpha}-maximal clique in an uncertain graph. We present matching upper and lower bounds on the number of {\alpha}-maximal cliques possible within an uncertain graph. We present an algorithm to enumerate {\alpha}-maximal cliques in an uncertain graph whose ...

Find SimilarView on arXiv

An upper bound for the clique number using clique ceiling numbers

June 3, 2019

85% Match
R. Dharmarajan, D. Ramachandran
Combinatorics

In this article we present the idea of clique ceiling numbers of the vertices of a given graph that has a universal vertex. We follow up with a polynomial-time algorithm to compute an upper bound for the clique number of such a graph using clique ceiling numbers. We compare this algorithm with some upper bound formulas for the clique number.

Find SimilarView on arXiv

What if CLIQUE were fast? Maximum Cliques in Information Networks and Strong Components in Temporal Networks

October 22, 2012

85% Match
Ryan A. Rossi, David F. Gleich, ... , Patwary Md. Mostofa Ali
Social and Information Netwo...
Distributed, Parallel, and C...
Discrete Mathematics
Physics and Society

Exact maximum clique finders have progressed to the point where we can investigate cliques in million-node social and information networks, as well as find strongly connected components in temporal networks. We use one such finder to study a large collection of modern networks emanating from biological, social, and technological domains. We show inter-relationships between maximum cliques and several other common network properties, including network density, maximum core, an...

Find SimilarView on arXiv

GraphCombEx: A Software Tool for Exploration of Combinatorial Optimisation Properties of Large Graphs

January 28, 2018

85% Match
David Chalupa, Ken A Hawick
Social and Information Netwo...
Mathematical Software

We present a prototype of a software tool for exploration of multiple combinatorial optimisation problems in large real-world and synthetic complex networks. Our tool, called GraphCombEx (an acronym of Graph Combinatorial Explorer), provides a unified framework for scalable computation and presentation of high-quality suboptimal solutions and bounds for a number of widely studied combinatorial optimisation problems. Efficient representation and applicability to large-scale gr...

Find SimilarView on arXiv

Counting primitive subsets and other statistics of the divisor graph of $\{1,2, \ldots n\}$

August 15, 2018

85% Match
Nathan McNew
Number Theory
Combinatorics

Let $Q(n)$ denote the count of the primitive subsets of the integers $\{1,2\ldots n\}$. We give a new proof that $Q(n) = \alpha^{(1+o(1))n}$ which allows us to give a good error term and to improve upon the lower bound for the value of this constant $\alpha$. We also show that the method developed can be applied to many similar problems that can be stated in terms of the divisor graph, including other questions about primitive sets, geometric-progression-free sets, and the di...

Find SimilarView on arXiv

Clique Graphs and Overlapping Communities

September 3, 2010

85% Match
T. S. Evans
Physics and Society
Social and Information Netwo...
Data Analysis, Statistics an...

It is shown how to construct a clique graph in which properties of cliques of a fixed order in a given graph are represented by vertices in a weighted graph. Various definitions and motivations for these weights are given. The detection of communities or clusters is used to illustrate how a clique graph may be exploited. In particular a benchmark network is shown where clique graphs find the overlapping communities accurately while vertex partition methods fail.

Find SimilarView on arXiv