independent set

(redirected from Maximum clique)

independent set

[‚in·di‚pen·dənt ′set]
(mathematics)
A set of vertices in a simple graph such that no two vertices in this set are adjacent. Also known as internally stable set.
References in periodicals archive ?
We use the (exact) maximum clique solving algorithm presented in [1], which is based on greedy graph colorings - i.e.
Their topics are graph theory, visualization with Microsoft foundation classes, graph coloring, computing the shortest path, computing the minimum spanning tree, computing the maximum clique, triangulation application, scheduling application, target detection application, and network routing application.
The clique number [omega](G) of a graph G is the number of vertices in a maximum clique in G.
In this paper, we are interested in finding a maximum clique in the visibility graph of a polygon.
In [4], the first three smallest values of the Laplacian spectral radii among all connected graphs with maximum clique size w are given.
In Carter et al.'s approach, their algorithm first found the maximum clique of conflicting examinations.
Additional Key Words and Phrases: Combinatorial optimization, Fortran subroutines, GRASP, local search, maximum clique, maximum independent set
With probability at least 1-[delta] the algorithm runs in O [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] time and returns a maximum clique, where [omega](G) is the number of vertices in a maximum clique in G.
Lemma 5 The MAXIMUM CLIQUE problem is NP-complete even for graphs with no clique separator.
Salvail, "Solvingthe maximum clique problem using a tabu search approach," Annals of Operations Research, vol.
By Theorem 5.5 and Lemma 5.2, the maximum clique size in G[L] is (1 - [epsilon])k, which is a contradiction.

Full browser ?