N 노드 및 인접 행렬이있는 지정된 무향 그래프의 경우, 노드 집합이 하나 이상의 노드가 있다고 가정합니다. 모든 노드 세트에있는 다른 사람들의 1 홉 이웃입니다. (n < N)인접 행렬에서 서로의 1- 홉 이웃 인 노드 집합 찾기
이러한 상황에서 이러한 노드 집합을 찾는 알고리즘은 무엇입니까?
예를 들어, a sample adjacency matrix (link: GitHub Gist)이고 42 노드입니다. 그리고 3 개의 노드가 서로 홉 홉 이웃 인 집합이 있다는 것이 알려져있다. 그러면 세트의 구성은 무엇입니까?
최종 목표는 9 1 홉 이웃 노드가 포함 된 세트를 찾으려면 약 450 노드로이 절차를 수행하는 것입니다. 따라서 확장 성 있고 효율적인 솔루션을 찾고 있습니다.
서로 이웃하는 그래프의 노드 집합은 클록 및 finding the largest clique in a graph, or indeed whether any clique of a specified size even exists in the graph이라고하며 고전적인 NP 하드 문제입니다.
FPT (고정 매개 변수 추적 가능) 문제라고하는 일부 NP 문제는 크기가 큰 문제 매개 변수가 작은 경우 큰 n에 대해서도 효율적으로 해결할 수 있습니다. 여기서 명백한 매개 변수는 가장 큰 파벌. 불행히도 Maximum Clique는이 매개 변수와 관련하여 FPT가 아니며 가장 잘 알려진 알고리즘은 n에서 지수 함수입니다. 몇몇은 Wikipedia 페이지에서 언급됩니다. 물론, 주어진 크기의 파벌이 이미 존재한다는 것을 알고 있기 때문에 운이 좋으면 휴리스틱으로 신속하게 찾을 수 있습니다.
참고 맥심 음 (최대 가능성) 맥심 알의 차이를 클리크 (성장 될 수 없다).