151:
74:
53:
22:
623:
that are passed into the recursive calls. In the lower levels of the recursion the algorithm switches to the pivoting version, with the pivots chosen to minimize the number of recursive calls as in the work of Tomita et al. (2006). We show that with this variant, and with some care in the data
172:
729:
We also have an implementation and computational experiments showing that it works well in practice but those are not published yet. Probably this work would not exist if I hadn't learned about the Bron–Kerbosch algorithm from my editing of the article here a year earlier.
558:(Paper by Cazals and Karande), I see that in their paper P := P \ {v} is done BEFORE calling BronKerbosch1 recursively while here it's done AFTER. I tried to implement the algorithm described here and I get infinite recursion in some cases. Should this be corrected here ?
612:
I and my co-authors have been studying a variant of the Bron–Kerbosch algorithm in which the outermost level of the recursion does not pivot, but instead orders the recursive calls that it makes using a
196:
336:
253:
191:
702:; Löffler, Maarten; Strash, Darren (2010), "Listing all maximal cliques in sparse graphs in near-optimal time", in Cheong, Otfried; Chwa, Kyung-Yong; Park, Kunsoo (eds.),
443:
The pseudo-code in Cazals and
Karande's paper (TCS, 2008, (407):564-568) worked better for me than the one presented in this page! The example contains a couple of typos.
782:
124:
114:
787:
90:
777:
298:
272:
137:
81:
58:
555:
361:
415:
244:
665:, analogous to the Moon–Moser bound on maximal cliques for graphs of unbounded degeneracy. For graphs of constant degeneracy (such as
516:
ok, but then the last sentence in the third paragraph of the example should read "Then, vertex 4 is added to X and removed from P".
225:
317:
745:
The implementation paper has been accepted to the 2011 Symposium on
Experimental Algorithmics, and can be found online at
282:
163:
33:
292:
206:
399:
This renders wrong in ie7. I'm guessing there are union and intersection etc. symbols but they all look like boxes.
327:
89:
related articles on
Knowledge. If you would like to participate, please visit the project page, where you can join
614:
354:
758:
735:
685:
578:
539:
507:
470:
433:
592:
563:
502:
Vertex 4 is moved into X during the iteration v=4, so that's why it's still in X during the iteration v=6. —
425:
411:
588:
559:
407:
263:
39:
523:
450:
403:
21:
754:
731:
574:
535:
503:
466:
429:
517:
496:
444:
746:
707:
762:
739:
596:
582:
567:
543:
527:
511:
474:
454:
437:
182:
717:
234:
86:
699:
462:
308:
150:
173:
Requested articles/Applied arts and sciences/Computer science, computing, and
Internet
771:
704:
21st
International Symposium on Algorithms and Computation (ISAAC 2010), Jeju, Korea
666:
721:
554:
Comparing the pseudo code given for BronKerbosch1 here to the one in Figure 1 of
694:
that is better than previously known FPT algorithms for the same problem. See:
706:, Lecture Notes in Computer Science, vol. 6506, Springer-Verlag, pp. 403–414,
215:
73:
52:
609:
I'm probably too close to this work to add it to the article myself, but:
659:
on the total size of all of the cliques for some graphs with degeneracy
624:
structures to make pivot selection fast, the worst case running time is
573:
It should be irrelevant as long as N(v) does not contain v itself. —
750:
712:
617:
for the graph. This ordering keeps down the sizes of the sets
291:
Find pictures for the biographies of computer scientists (see
15:
556:
ftp://ftp-sop.inria.fr/geometrica/fcazals/papers/ncliques.pdf
644:
is its degeneracy. This nearly matches a lower bound of
426:
Help:Special characters#Displaying
Special Characters
85:, a collaborative effort to improve the coverage of
197:Computer science articles needing expert attention
638:is the number of vertices in the given graph and
337:WikiProject Computer science/Unreferenced BLPs
8:
424:It does contain set notation. You may find
254:Computer science articles without infoboxes
192:Computer science articles needing attention
158:Here are some tasks awaiting attention:
132:
47:
711:
479:I may be wrong but, in the example, when
783:Mid-importance Computer science articles
49:
19:
684:, and more generally the algorithm is
99:Knowledge:WikiProject Computer science
788:WikiProject Computer science articles
102:Template:WikiProject Computer science
7:
79:This article is within the scope of
688:with a dependence on the parameter
38:It is of interest to the following
273:Timeline of computing 2020–present
14:
778:B-Class Computer science articles
299:Computing articles needing images
149:
72:
51:
20:
487:) the recursive call should be
119:This article has been rated as
1:
597:15:27, 31 December 2010 (UTC)
583:16:22, 30 December 2010 (UTC)
568:12:38, 30 December 2010 (UTC)
353:Tag all relevant articles in
93:and see a list of open tasks.
740:06:11, 22 January 2011 (UTC)
722:10.1007/978-3-642-17517-6_36
605:Fixed parameter tractability
362:WikiProject Computer science
138:WikiProject Computer science
82:WikiProject Computer science
587:Good point, you're right !
463:You're welcome to fix them.
293:List of computer scientists
804:
763:22:51, 15 March 2011 (UTC)
125:project's importance scale
686:fixed-parameter tractable
544:15:07, 19 July 2010 (UTC)
528:14:45, 19 July 2010 (UTC)
512:14:20, 19 July 2010 (UTC)
355:Category:Computer science
131:
118:
105:Computer science articles
67:
46:
493:BronKerbosch2({6},Ø,{4})
489:BronKerbosch2({6},{4},Ø)
475:20:15, 4 July 2010 (UTC)
455:20:02, 4 July 2010 (UTC)
438:04:43, 9 June 2010 (UTC)
357:and sub-categories with
676:) the running time is
318:Computer science stubs
28:This article is rated
483:(third iteration for
534:Good catch. Fixed. —
136:Things you can help
615:degeneracy ordering
34:content assessment
520:, 19 July 2010.
420:
406:comment added by
392:
391:
388:
387:
384:
383:
380:
379:
376:
375:
795:
724:
715:
693:
683:
675:
664:
658:
643:
637:
631:
622:
531:
499:, 19 July 2010.
494:
490:
486:
482:
458:
447:, 4 July 2010.
428:to be helpful. —
419:
400:
366:
360:
235:Computer science
164:Article requests
153:
146:
145:
133:
107:
106:
103:
100:
97:
96:Computer science
87:Computer science
76:
69:
68:
63:
59:Computer science
55:
48:
31:
25:
24:
16:
803:
802:
798:
797:
796:
794:
793:
792:
768:
767:
700:Eppstein, David
698:
689:
677:
670:
660:
645:
639:
633:
625:
618:
607:
521:
492:
488:
484:
480:
448:
401:
397:
372:
369:
364:
358:
346:Project-related
341:
322:
303:
277:
258:
239:
220:
201:
177:
104:
101:
98:
95:
94:
61:
32:on Knowledge's
29:
12:
11:
5:
801:
799:
791:
790:
785:
780:
770:
769:
766:
765:
755:David Eppstein
732:David Eppstein
727:
726:
606:
603:
602:
601:
600:
599:
575:David Eppstein
553:
551:
550:
549:
548:
547:
546:
536:David Eppstein
526:comment added
514:
504:David Eppstein
491:, rather than
477:
467:David Eppstein
453:comment added
441:
440:
430:David Eppstein
396:
393:
390:
389:
386:
385:
382:
381:
378:
377:
374:
373:
371:
370:
368:
367:
350:
342:
340:
339:
333:
323:
321:
320:
314:
304:
302:
301:
296:
288:
278:
276:
275:
269:
259:
257:
256:
250:
240:
238:
237:
231:
221:
219:
218:
212:
202:
200:
199:
194:
188:
178:
176:
175:
169:
157:
155:
154:
142:
141:
129:
128:
121:Mid-importance
117:
111:
110:
108:
91:the discussion
77:
65:
64:
62:Mid‑importance
56:
44:
43:
37:
26:
13:
10:
9:
6:
4:
3:
2:
800:
789:
786:
784:
781:
779:
776:
775:
773:
764:
760:
756:
752:
748:
744:
743:
742:
741:
737:
733:
723:
719:
714:
709:
705:
701:
697:
696:
695:
692:
687:
681:
673:
669:, which have
668:
667:planar graphs
663:
656:
652:
648:
642:
636:
629:
621:
616:
610:
604:
598:
594:
590:
589:Andre.holzner
586:
585:
584:
580:
576:
572:
571:
570:
569:
565:
561:
560:Andre.holzner
557:
545:
541:
537:
533:
532:
529:
525:
519:
515:
513:
509:
505:
501:
500:
498:
478:
476:
472:
468:
464:
461:
460:
459:
456:
452:
446:
439:
435:
431:
427:
423:
422:
421:
417:
413:
409:
408:192.91.147.34
405:
394:
363:
356:
352:
351:
349:
347:
343:
338:
335:
334:
332:
330:
329:
324:
319:
316:
315:
313:
311:
310:
305:
300:
297:
294:
290:
289:
287:
285:
284:
279:
274:
271:
270:
268:
266:
265:
260:
255:
252:
251:
249:
247:
246:
241:
236:
233:
232:
230:
228:
227:
222:
217:
214:
213:
211:
209:
208:
203:
198:
195:
193:
190:
189:
187:
185:
184:
179:
174:
171:
170:
168:
166:
165:
160:
159:
156:
152:
148:
147:
144:
143:
139:
135:
134:
130:
126:
122:
116:
113:
112:
109:
92:
88:
84:
83:
78:
75:
71:
70:
66:
60:
57:
54:
50:
45:
41:
35:
27:
23:
18:
17:
728:
703:
690:
679:
671:
661:
654:
650:
646:
640:
634:
627:
619:
611:
608:
552:
518:Michele Zito
497:Michele Zito
445:Michele Zito
442:
398:
345:
344:
328:Unreferenced
326:
325:
307:
306:
281:
280:
262:
261:
243:
242:
224:
223:
205:
204:
181:
180:
162:
161:
120:
80:
40:WikiProjects
522:—Preceding
449:—Preceding
402:—Preceding
772:Categories
751:1103.0318
713:1006.5440
216:Computing
632:, where
416:contribs
404:unsigned
395:Untitled
264:Maintain
207:Copyedit
524:undated
451:undated
245:Infobox
183:Cleanup
123:on the
30:B-class
226:Expand
36:scale.
747:arXiv
708:arXiv
309:Stubs
283:Photo
140:with:
759:talk
736:talk
593:talk
579:talk
564:talk
540:talk
508:talk
471:talk
434:talk
412:talk
753:. —
718:doi
674:≤ 5
485:u=2
481:v=6
115:Mid
774::
761:)
738:)
716:,
678:O(
657:)3
653:−
630:3)
628:dn
626:O(
595:)
581:)
566:)
542:)
510:)
495:?
473:)
436:)
418:)
414:•
365:}}
359:{{
757:(
749::
734:(
730:—
725:.
720::
710::
691:d
682:)
680:n
672:d
662:d
655:d
651:n
649:(
647:d
641:d
635:n
620:P
591:(
577:(
562:(
538:(
530:.
506:(
469:(
465:—
457:.
432:(
410:(
348::
331::
312::
295:)
286::
267::
248::
229::
210::
186::
167::
127:.
42::
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
