Is a given graph a k-plex? (similiar to clique)
My problem is the following:
I need to find an algorithm or at least an idea, how to find out in
efficient time if a given graph is a k-plex.
(Quote: "A k-plex is a maximal subgraph with the following property: each
vertex of the induced subgraph is connected to at least n-k other
vertices, where n is the number of vertices in the induced
subgraph."[http://www.analytictech.com/ucinet/help/1pdb_fw.htm])
Is there anything better than just checking if each node is connected to
n-k other nodes?
I would appreciate any help. Thanks in advance.
No comments:
Post a Comment