Talk:Bron–Kerbosch algorithm

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.

Talk:Bron–Kerbosch algorithm

Untitled

Latest comment: 15 years ago9 comments3 people in discussion

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

Latest comment: 15 years ago2 comments1 person in discussion

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(dn3d/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)3d/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 ≤ 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

Content Disclaimer

Informasi ini disarikan dari Wikipedia dan disajikan kembali untuk tujuan edukasi. Konten tersedia di bawah lisensi CC BY-SA 3.0. Kami tidak bertanggung jawab atas ketidakakuratan data yang bersumber dari kontribusi publik tersebut.

  1. The information displayed on this website is sourced in part or in whole from Wikipedia and has been adapted for the purpose of restating it. We strive to provide accurate and relevant information, however:
  2. There is no guarantee of absolute accuracy. Wikipedia is an open, collaborative project that can be edited by anyone, so information is subject to change.
  3. It is not intended to constitute professional advice. The content displayed is for informational and educational purposes only. For important decisions (e.g., medical, legal, or financial), please consult a professional.
  4. Content copyright. Wikipedia is licensed under the Creative Commons Attribution-ShareAlike License (CC BY-SA). This means that content may be reused with appropriate attribution and shared under a similar license.
  5. Responsible use. Any risk arising from the use of information from this website is entirely the responsibility of the user.