liveBook · Manning

Chapter 11: Bron-Kerbosch Algorithm

What you will learn in chapter 11 of Algorithms Every Programmer Should Know

The introduction shifts from maximum flow to finding mutually connected groups in a graph and gives a high-level account of Bron–Kerbosch’s backtracking approach.

After this chapter you will be able to

What it builds on

Section by section

Introduction

The introduction shifts from maximum flow to finding mutually connected groups in a graph and gives a high-level account of Bron–Kerbosch’s backtracking approach.

Key terms: maximum flow, graph clustering, maximal clique, backtracking, Bron–Kerbosch algorithm

11.1 What is a clique?

This section defines maximal cliques and traces how Bron–Kerbosch finds them through recursive set intersections, backtracking, and pivoting.

Key terms: clique, complete subgraph, Maximal Clique, brute force, power set, time complexity, R, P, X, set intersections

11.2 Real-world applications

The section shows how clique finding supports feature matching, molecular comparison, and general-purpose graph software.

Key terms: stereo correspondence, compatibility graph, candidate correspondences, geometrically consistent, clique, correspondence graph, atom pairings, Maximum Common Subgraph (MCS), maximum common substructure, Bron–Kerbosch

11.3 Key Insights

This section explains Bron–Kerbosch’s output-bound efficiency, depth-first memory use, sensitivity to graph density, and use of the excluded set X to avoid duplicate work.

Key terms: pivoting, maximal cliques, worst-case runtime, theoretically optimal, depth-first, recursion stack, O(V) space complexity, candidate subsets, graph density, sparse

11.4 Summary

11.5 References

Lists code, video, documentation, and research references related to the Bron–Kerbosch algorithm and clique detection.

Where this is used later

Concepts explained in this chapter

← Chapter 10: Push Relabel Algorithm Chapter 12: A* Algorithm →

These guides are generated from the text of Manning books by Manning's knowledge graph and link to the sections they draw on. The full books are available on liveBook and at manning.com.