Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- # Returns false if G does not have a clique of size k. Otherwise it returns G. Note
- # that returning G does not necesarily implies G has a clique of size >= k.
- def hasLargeClique(G,k):
- n = G.order()
- if n < 250:
- c = G.clique_number()
- if c < k :
- return false
- return G
- O = G.automorphism_group(return_group=false, orbits=True)
- o = min(O, key=lambda x: G.degree(x[0]))
- v = o[0]
- ret = hasLargeClique(subgraph(G, G[v]), k - 1)
- if ret: return G
- H = G.copy()
- H.delete_vertices(o)
- return hasLargeClique(H,k)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement