Finding Cliques of a Graph using Prime Numbers

In this paper, we study the maximum clique problem on hyperbolic random graphs. A hyperbolic random graph is a mathematical model for analyzing scale-free networks since it effectively explains the power-law degree distribution of scale-free networks. We propose a simple algorithm for finding a maximum clique in hyperbolic random graph. We first analyze the running time of our algorithm theoretically. We can compute a maximum clique on a hyperbolic random graph $G$ in $O(m + ...

Finding a Maximum Clique is a classic property test from graph theory; find any one of the largest complete subgraphs in an Erd\"os-R\'enyi G(N, p) random graph. We use Maximum Clique to explore the structure of the problem as a function of N, the graph size, and K, the clique size sought. It displays a complex phase boundary, a staircase of steps at each of which 2log2 N and Kmax, the maximum size of a clique that can be found, increases by 1. Each of its boundaries has a fi...

Maximum Flow Network Interdiction Problem (MFNIP) is known to be strongly NP-hard problem. We solve a simple form of MFNIP in polynomial time. We review the reduction of MFNIP from the clique problem. We propose a polynomial time solution to the Clique Problem.

In this short paper, following the most recent advances in complex network theory, a new approach to number theory with potential applications to other fields is proposed. The model by Garcia-Perez, Serrano and Boguna, introduces an algorithm which allows to create a bipartite graph of integers (with primes and composites) statistically very close to the real one. Since the algorithm is defined a priori, we can have a description of the simulated prime number distribution in ...

We consider the maintenance of the set of all maximal cliques in a dynamic graph that is changing through the addition or deletion of edges. We present nearly tight bounds on the magnitude of change in the set of maximal cliques, as well as the first change-sensitive algorithms for clique maintenance, whose runtime is proportional to the magnitude of the change in the set of maximal cliques. We present experimental results showing these algorithms are efficient in practice an...

Finding the clique of maximum cardinality in an arbitrary graph is an NP-Hard problem that has many applications, which has motivated studies to solve it exactly despite its difficulty. The great majority of algorithms proposed in the literature are based on the Branch and Bound method. In this paper, we propose an exact algorithm for the maximum clique problem based on the Russian Dolls Search method. When compared to Branch and Bound, the main difference of the Russian Doll...

A graph $G$ is defined encapsulating the number theoretic notion of the Fundamental Theorem of Arithmetic. We then provide a graph theoretic approach to the fundamental results on the coprimality of two natural numbers, through the use of an adjacency operator $\hat{\mathbf{A}}(G)$. Lastly, these results are used to give an alternate proof to the known result that there are infinitely many primes in the natural numbers $\mathbb{N}$.

Finding maximum cliques in large networks is a challenging combinatorial problem with many real-world applications. We present a fast algorithm to achieve the exact solution for the maximum clique problem in large sparse networks based on efficient graph decomposition. A bunch of effective techniques is being used to greatly prune the graph and a novel concept called Complete-Upper-Bound-Induced Subgraph (CUBIS) is proposed to ensure that the structures with the potential to ...

Let $\mathbb{N}_0$ be the set of all non-negative integers and $\mathcal{P}(\mathbb{N}_0)$ be its power set. An integer additive set-indexer (IASI) is defined as an injective function $f:V(G)\to \mathcal{P}(\mathbb{N}_0)$ such that the induced function $f^+:E(G) \to \mathcal{P}(\mathbb{N}_0)$ defined by $f^+(uv) = f(u)+ f(v)$ is also injective, where $\mathbb{N}_0$ is the set of all non-negative integers. A graph $G$ which admits an IASI is called an IASI graph. An IASI of a ...

The theorem presented in this paper allows the creation of large prime numbers (of order up to o(n^2)) given a table of all primes up to n.