ID: cs/0601117

Finding Cliques of a Graph using Prime Numbers

January 27, 2006

View on ArXiv
Dhananjay D. Kulkarni, Shekhar Verma, Prashant
Computer Science
Data Structures and Algorith...

This paper proposes a new algorithm for solving maximal cliques for simple undirected graphs using the theory of prime numbers. A novel approach using prime numbers is used to find cliques and ends with a discussion of the algorithm.

Similar papers 1

A Polynomial Time Algorithm For Solving Clique Problems

March 10, 2015

92% Match
Michael LaPlante
Data Structures and Algorith...

I present a single algorithm which solves the clique problems, "What is the largest size clique?", "What are all the maximal cliques?" and the decision problem, "Does a clique of size k exist?" for any given graph in polynomial time. The existence of this algorithm proves that P = NP.

Find SimilarView on arXiv

A Polynomial Time Solution to the Clique Problem

February 21, 2014

90% Match
Pawan Tamta, B. P. Pande, H. S. Dhami
Data Structures and Algorith...
Optimization and Control

The Clique Problem has a reduction to the Maximum Flow Network Interdiction Problem. We review the reduction to evolve a polynomial time algorithm for the Clique Problem. A computer program in C language has been written to validate the easiness of the algorithm.

Find SimilarView on arXiv

Is it possible to find the maximum clique in general graphs?

October 24, 2011

90% Match
José Ignacio Alvarez-Hamelin
Data Structures and Algorith...
Computational Complexity
Discrete Mathematics

Finding the maximum clique is a known NP-Complete problem and it is also hard to approximate. This work proposes two efficient algorithms to obtain it. Nevertheless, the first one is able to fins the maximum for some special cases, while the second one has its execution time bounded by the number of cliques that each vertex belongs to.

Find SimilarView on arXiv

A Novel Approach Applied to the Largest Clique Problem

September 18, 2002

89% Match
Vladimir Gudkov, Shmuel Nussinov, Zohar Nussinov
Discrete Mathematics
Combinatorics
Computational Physics

A novel approach to complex problems has been previously applied to graph classification and the graph equivalence problem. Here we apply it to the NP complete problem of finding the largest perfect clique within a graph $G$.

Find SimilarView on arXiv

Fast Algorithms for the Maximum Clique Problem on Massive Sparse Graphs

September 26, 2012

89% Match
Bharath Pattabiraman, Md. Mostofa Ali Patwary, Assefaw H. Gebremedhin, ... , Choudhary Alok
Data Structures and Algorith...
Information Retrieval

The maximum clique problem is a well known NP-Hard problem with applications in data mining, network analysis, informatics, and many other areas. Although there exist several algorithms with acceptable runtimes for certain classes of graphs, many of them are infeasible for massive graphs. We present a new exact algorithm that employs novel pruning techniques to very quickly find maximum cliques in large sparse graphs. Extensive experiments on several types of synthetic and re...

Find SimilarView on arXiv

On the tractability of the maximum clique problem

March 26, 2019

89% Match
R. Dharmarajan, D. Ramachandran
Data Structures and Algorith...

The maximum clique problem is a classical NP-complete problem in graph theory and has important applications in many domains. In this paper we show, in a partially non-constructive way, the existence of an exact polynomial-time algorithm for this problem. We outline the algorithm in pseudo-code style. Then we prove its exactness and efficiency by analysis.

Find SimilarView on arXiv

Finding Maximum Cliques in Large Networks

July 26, 2022

88% Match
S. Y. Chan, K. Morgan, J. Ugon
Social and Information Netwo...
Combinatorics

There are many methods to find a maximum (or maximal) clique in large networks. Due to the nature of combinatorics, computation becomes exponentially expensive as the number of vertices in a graph increases. Thus, there is a need for efficient algorithms to find a maximum clique. In this paper, we present a graph reduction method that significantly reduces the order of a graph, and so enables the identification of a maximum clique in graphs of large order, that would otherwis...

Find SimilarView on arXiv

Fast Algorithms for the Maximum Clique Problem on Massive Graphs with Applications to Overlapping Community Detection

November 27, 2014

88% Match
Bharath Pattabiraman, Md. Mostofa Ali Patwary, Assefaw H. Gebremedhin, ... , Choudhary Alok
Data Structures and Algorith...
Social and Information Netwo...

The maximum clique problem is a well known NP-Hard problem with applications in data mining, network analysis, information retrieval and many other areas related to the World Wide Web. There exist several algorithms for the problem with acceptable runtimes for certain classes of graphs, but many of them are infeasible for massive graphs. We present a new exact algorithm that employs novel pruning techniques and is able to find maximum cliques in very large, sparse graphs quic...

Find SimilarView on arXiv

Algorithmic methods of finite discrete structures. Graph clique problem

October 29, 2024

88% Match
Sergey Kurapov, Maxim Davidovsky
Discrete Mathematics
Computational Complexity
Combinatorics

The monography presents a new algorithm for finding the clique of maximal length in a nonseparable graph. The algorithm is based on the properties of the representation of a clique as a subset of the set of cycles with a length of three, the ring sum of which is an empty set. As a result of selecting the cycles of the length of three, two vectors are formed: the vector of cycles passing through the edges and the vector of cycles passing through the vertices. The numerical val...

Find SimilarView on arXiv

Listing All Maximal Cliques in Large Sparse Real-World Graphs

March 2, 2011

87% Match
David Eppstein, Darren Strash
Data Structures and Algorith...

We implement a new algorithm for listing all maximal cliques in sparse graphs due to Eppstein, L\"offler, and Strash (ISAAC 2010) and analyze its performance on a large corpus of real-world graphs. Our analysis shows that this algorithm is the first to offer a practical solution to listing all maximal cliques in large sparse graphs. All other theoretically-fast algorithms for sparse graphs have been shown to be significantly slower than the algorithm of Tomita et al. (Theoret...

Find SimilarView on arXiv