| Calling Sequence | Clique(A)
| |||||||||
| Parameters |
| |||||||||
| Return Type | set | |||||||||
| Globals | CliqueUpperBound, | |||||||||
| Synopsis | The input to this algorithm is an undirected graph. An undirected graph is represented as a Graph data structure which should accept two selectors: Nodes and Edges. The Maximum Clique problem is finding a set of completely connected vertices which is of maximum size. | |||||||||
The output is a set of the Nodes in the clique. The algorithm computes an upper bound on the size of the maximum clique which is left in the global variable CliqueUpperBound. If this coincides with the size of the answer, it means that the answer is optimal (maximal). The global variable CliqueIterFactor may be assigned a non-negative number f. The algorithm will then run for f*n^2 iterations. If f=0 then only the greedy heuristic is run, and this is quite fast. The larger f, the more accurate the answers will be, and the more time the algorithm will consume. | ||||||||||
The Clique problem is closely related to the Vertex Cover problem. They can be related by the following formula: | ||||||||||
Clique(G) = NodeComplement(VertexCover(EdgeComplement(G))) | ||||||||||
| Examples | > hex := HexahedronGraph(); hex := Graph(Edges(Edge(0,1,2),Edge(0,1,4),Edge(0,1,5),Edge(0,2,3),Edge(0,2,6),E dge(0,3,4),Edge(0,3,7),Edge(0,4,8),Edge(0,5,6),Edge(0,5,8),Edge(0,6,7),Edge(0,7, 8)),Nodes(1,2,3,4,5,6,7,8)) > Clique(hex); {7,8}
| |||||||||
| See also | BipartiteGraph, DrawGraph, Edge, EdgeComplement, Edges, FindConnectedComponents, Graph, Graph_Rand, InduceGraph, MaxCut, MaxEdgeWeightClique, MST, Nodes, Path, RegularGraph, ShortestPath, TetrahedronGraph, VertexCover | |||||||||