Talk:Bron–Kerbosch algorithm

This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.Computer scienceWikipedia:WikiProject Computer scienceTemplate:WikiProject Computer scienceComputer science articles

Mid

This article has been rated as Mid-importance on the project's importance scale.

Things you can help WikiProject Computer science with:

Here are some tasks awaiting attention:

Article requests :
- Requested articles/Applied arts and sciences/Computer science, computing, and Internet
Cleanup :
- Computer science articles needing attention
- Computer science articles needing expert attention
Copyedit :
- Computing
Expand :
- Computer science
Infobox :
- Computer science articles without infoboxes
Maintain :
- Timeline of computing 2020–present
Photo :
- Find pictures for the biographies of computer scientists (see List of computer scientists)
- Computing articles needing images
Stubs :
- Computer science stubs
Unreferenced :
- WikiProject Computer science/Unreferenced BLPs
Project-related :
- Tag all relevant articles in Category:Computer science and sub-categories with {{WikiProject Computer science}}

Untitled[edit]

This renders wrong in ie7. I'm guessing there are union and intersection etc. symbols but they all look like boxes. —Preceding unsigned comment added by 192.91.147.34 (talk • contribs)

It does contain set notation. You may find Help:Special characters#Displaying Special Characters to be helpful. —David Eppstein (talk) 04:43, 9 June 2010 (UTC)[reply]

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. Michele Zito, 4 July 2010. —Preceding undated comment added 20:02, 4 July 2010 (UTC).[reply]

You're welcome to fix them. —David Eppstein (talk) 20:15, 4 July 2010 (UTC)[reply]

I may be wrong but, in the example, when v=6 (third iteration for u=2) the recursive call should be BronKerbosch2({6},{4},Ø), rather than BronKerbosch2({6},Ø,{4})? Michele Zito, 19 July 2010.

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. —David Eppstein (talk) 14:20, 19 July 2010 (UTC)[reply]

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". Michele Zito, 19 July 2010. —Preceding undated comment added 14:45, 19 July 2010 (UTC).[reply]

Good catch. Fixed. —David Eppstein (talk) 15:07, 19 July 2010 (UTC)[reply]

Comparing the pseudo code given for BronKerbosch1 here to the one in Figure 1 of ftp://ftp-sop.inria.fr/geometrica/fcazals/papers/ncliques.pdf (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 ? Andre.holzner (talk) 12:38, 30 December 2010 (UTC)[reply]

It should be irrelevant as long as N(v) does not contain v itself. —David Eppstein (talk) 16:22, 30 December 2010 (UTC)[reply]

Good point, you're right ! Andre.holzner (talk) 15:27, 31 December 2010 (UTC)[reply]

Fixed parameter tractability[edit]

I'm probably too close to this work to add it to the article myself, but:

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 degeneracy ordering for the graph. This ordering keeps down the sizes of the sets $P$ 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 structures to make pivot selection fast, the worst case running time is $O(dn 3 d /3)$ , where $n$ is the number of vertices in the given graph and $d$ is its degeneracy. This nearly matches a lower bound of $d (n - d)3 d /3$ on the total size of all of the cliques for some graphs with degeneracy $d$ , analogous to the Moon–Moser bound on maximal cliques for graphs of unbounded degeneracy. For graphs of constant degeneracy (such as planar graphs, which have $d \leq 5$ ) the running time is $O(n)$ , and more generally the algorithm is fixed-parameter tractable with a dependence on the parameter $d$ that is better than previously known FPT algorithms for the same problem. See:

Eppstein, David; 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.), 21st International Symposium on Algorithms and Computation (ISAAC 2010), Jeju, Korea, Lecture Notes in Computer Science, vol. 6506, Springer-Verlag, pp. 403–414, arXiv:1006.5440, doi:10.1007/978-3-642-17517-6_36.

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. —David Eppstein (talk) 06:11, 22 January 2011 (UTC)[reply]

The implementation paper has been accepted to the 2011 Symposium on Experimental Algorithmics, and can be found online at arXiv:1103.0318. —David Eppstein (talk) 22:51, 15 March 2011 (UTC)[reply]