Problem 2647. Find the maximal cliques in an undirected graph
This is a variant of a previous problem on maximal cliques. Instead of simply computing the number of maximal cliques in an undirected graph, now you must return the cliques themselves.
Given an NxN adjacency matrix (A) for an undirected graph with N vertices, return an array (C) in which each column encodes one of the maximal cliques in the graph. If C(i,j) = 1, then the ith vertex in the graph is included in the jth clique. The order of columns does not matter, but all maximal cliques must be given - that is, size(C,2) should equal the number of maximal cliques.
Example
Consider the graph shown below,
which has the following adjacency matrix:
A = [ 0 1 0 0 0 1 0 1 1 0 0 1 0 1 0 0 1 1 0 1 0 0 0 1 0 ]
The maximal cliques are {1,2}, {2,3,4}, and {4,5}. Therefore, one (of three) valid outputs is:
C = [ 1 0 0 1 1 0 0 1 0 0 1 1 0 0 1 ]
NOTE: You may assume the data type of the adjacency matrix (A) is double.
Solution Stats
Problem Comments
-
1 Comment
test suite 3 prevented my brute-force :(
Solution Comments
Show commentsProblem Recent Solvers5
Suggested Problems
-
Find the numeric mean of the prime numbers in a matrix.
8892 Solvers
-
2017 Solvers
-
The Goldbach Conjecture, Part 2
2325 Solvers
-
1594 Solvers
-
330 Solvers
More from this Author44
Problem Tags
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!