🐬 Named Algorithms

Every algorithm, data structure, theorem or construction known by a name (about 400, grouped by first letter; use the table of contents to jump), with what it does and where it lives in these notes. For “which algorithm solves which problem in what time”, see the 🐬 Complexity Cheat Sheet; for famous problems, see 🐬 Classic Problems.

A

Name	What it does	Note
A* search	shortest path guided by an admissible heuristic	Informed Search
Ackermann function (inverse α)	the near-constant factor in DSU and MST bounds	Disjoint Set Union
Adaptive Simpson	numerical integration with Richardson correction	Root Finding and Integration
AM–GM–HM inequality	arithmetic mean $\ge$ geometric mean $\ge$ harmonic mean, equality iff all terms equal	🐬 Formula
Agrawal–Kayal–Saxena (AKS)	first deterministic polynomial-time primality test	Theoretical Algorithms Catalog
Aho–Corasick automaton	multi-pattern matching with suffix links	Trie and Aho–Corasick
Aho–Corasick	many-pattern matching with an automaton of failure links	Trie and Aho-Corasick
Aho–Hopcroft–Ullman	linear-time rooted tree isomorphism (the AHU canonical labels)	Tree Isomorphism and Prüfer Codes
AHU encoding	canonical form of rooted trees, tree isomorphism	Tree Isomorphism
Ahuja–Orlin	scaling max-flow and min-cost flow algorithms	Theoretical Algorithms Catalog
Aldous–Broder	uniform random spanning tree by a random walk	Matrix-Tree Theorem
Aliens trick (WQS binary search, Lagrangian relaxation)	remove a “exactly $k$” constraint by penalising	Aliens Trick
Andrew’s monotone chain	convex hull in $O(n\log n)$	Convex Hull
André’s reflection principle	lattice paths with one or two boundaries	Catalan and Lattice Paths
Apostolico–Giancarlo	Boyer–Moore variant with at most $2n$ comparisons	Theoretical Algorithms Catalog
Appel–Haken (four colour theorem)	every planar graph is 4-colourable	Special Graph Classes
Arpa’s trick	offline RMQ with a DSU in $O(\alpha )$ per query	Range Minimum Query

B

Name	What it does	Note
Baby-step giant-step	discrete logarithm in $O(\sqrt{m})$	Discrete Log
Bernoulli’s inequality	$(1+x{)}^r\ge 1+rx$ for $x>-1$, $r\ge 1$	🐬 Formula
Beatty’s theorem	$\lfloor n\phi \rfloor$ and $\lfloor n{\phi }^2\rfloor$ partition the positive integers	Sprague–Grundy
BEST theorem	counts Eulerian circuits as arborescences times $\prod ({\mathrm{deg}}^{+}-1)!$	Euler Tours
Baeza-Yates–Gonnet (Shift-And / Shift-Or)	bit-parallel string matching in $O(n\lceil m/w\rceil )$	Other Pattern Matching
Ballot problem (Bertrand)	probability one candidate stays strictly ahead: $\frac{a-b}{a+b}$	Catalan Numbers and Lattice Paths
Banach–Knaster (last diminisher)	proportional cake division for $n$ people	Cake Cutting
Barbier’s theorem	every curve of constant width $w$ has perimeter $\pi w$	Buffon’s Needle
Bareiss algorithm	fraction-free exact integer determinant	Determinants
Bareiss elimination	fraction-free integer determinant	Determinants and Permanents
Barnes–Hut	$O(n\log n)$ approximate $n$-body forces with a quadtree	KD-Tree and Spatial Structures
Barrett reduction	division-free modular reduction for run-time moduli	Barrett and Montgomery
Baum–Welch	EM training of hidden Markov models	DAG and Expected-Value DP
Bayes’ theorem	$P(A\mid B)=P(B\mid A)P(A)/P(B)$	Probability and Expectation
Bell triangle	Bell numbers in O(n^2)	Stirling, Bell and Partitions
Bell triangle, Bell numbers	number of set partitions	Counting Fundamentals
Bellman–Ford	shortest paths with negative edges, negative-cycle detection	Shortest Paths
Bellman–Held–Karp	bitmask DP for TSP in $O(2^n{n}^2)$	Hamiltonian Paths and TSP
Benczúr–Karger	graph sparsification preserving all cuts	Global Minimum Cut
Bender–Farach-Colton	$O(n)$ / $O(1)$ LCA and RMQ via ±1 RMQ	Range Minimum Query
Bentley–Shamos	divide-and-conquer closest pair in $O(n\log n)$	Closest Pair
Berge’s theorem	a matching is maximum iff it has no augmenting path	Bipartite Matching
Berkman–Vishkin	parallel and linear-time RMQ / LCA	Theoretical Algorithms Catalog
Berlekamp’s algorithm	deterministic factorisation over small finite fields	Polynomial Factorization
Berlekamp’s rule (Blue-Red stalks)	value of a Hackenbush stalk from its colour sequence	Hackenbush
Berlekamp–Massey algorithm	shortest linear recurrence of a sequence	Linear Recurrences
Berlekamp–Massey	shortest linear recurrence of a sequence	Linear Recurrences
Bernstein–Nanongkai–Wulff-Nilsen	near-linear negative-weight shortest paths	Theoretical Algorithms Catalog
Binet’s formula	closed form $F_n=({\phi }^n-{\psi }^n)/\sqrt{5}$	Generating Functions
Birthday paradox	collisions after $\Theta (\sqrt{N})$ random samples	Probability and Expectation
Bitap (shift-and)	bit-parallel exact and approximate matching	Other Matching
Bitset (word-RAM) tricks	$w$-fold speedups of DP and set operations	Bitset
Björklund’s hafnian algorithm	weighted perfect matchings of a general graph in O(n^4 2^(n/2))	Determinants
Björklund–Husfeldt–Koivisto	chromatic number / set cover in $O^{\ast }(2^n)$ by inclusion–exclusion	Graph Coloring
Bland’s rule	anti-cycling pivot rule for the simplex method	Linear Programming
Block-cut tree	tree of biconnected components and cut vertices	Bridges and Biconnectivity
Bloom filter	set membership with false positives only	Sampling and Streaming
Blossom (Edmonds)	maximum matching in general graphs	General Matching
Bluestein (chirp-z)	DFT of arbitrary length via convolution	Convolution Variants
Bluestein’s algorithm	DFT of arbitrary length as a convolution	Convolution Variants
Boesch–Tindell	which mixed graphs have a strongly connected orientation	Bridges and Biconnectivity
Bondy–Chvátal closure	Hamiltonicity via degree-sum closure	Hamiltonian Paths and TSP
Bonferroni inequalities	truncated inclusion–exclusion gives alternating bounds	Inclusion–Exclusion
Booth / minimal rotation	lexicographically least rotation in $O(n)$	Lyndon Words
Booth’s algorithm	least rotation of a string	Lyndon Words
Borůvka	MST in $O(m\log n)$, parallel-friendly	MST
Bose construction	Steiner triple system on $v\equiv 3(\mathrm{mod}6)$ points from an idempotent quasigroup	Kirkman’s Schoolgirls
Bose–Nelson	sorting networks for small $n$	Sorting, Selection and Inversions
Bostan–Mori algorithm	[x^n] P/Q in O(k log k log n)	Linear Recurrences
Bostan–Mori	$k$-th term of a linear recurrence in $O(d\log d\log k)$	Linear Recurrences
Bouton’s theorem	Nim position is losing iff the XOR of heaps is 0	Combinatorial Games and Nim
Bowyer–Watson	incremental Delaunay triangulation	Delaunay and Voronoi
Boyer–Moore algorithm	right-to-left matching with bad-character and good-suffix shifts	Other Matching
Boyer–Moore majority vote	majority element in $O(1)$ space	Classic Array Problems
Boyer–Moore–Galil	Boyer–Moore with a linear worst case	Theoretical Algorithms Catalog
Boyer–Moore–Horspool	simplified Boyer–Moore with the bad-character rule only	Other Pattern Matching
Boyer–Myrvold	linear-time planarity testing and embedding	Special Graph Classes
Brent’s cycle detection	cycle detection with fewer evaluations than Floyd	Functional Graphs
Brent–Kung composition	f(g(x)) by baby-step giant-step	Composition and Taylor Shift
Brent–Kung	power-series composition in $O((n\log n{)}^{1.5})$	Composition and Taylor Shift
Broken profile DP	grid tiling DP over a cell-by-cell frontier	Broken Profile DP
Bron–Kerbosch	maximal clique enumeration with pivoting	Maximum Clique and Independent Set
Buffon’s needle	crossing probability $\frac{2\ell }{\pi d}$; Monte Carlo estimate of $\pi$	Buffon’s Needle
Burnside / Pólya	counting up to symmetry	Burnside and Pólya
Burrows–Wheeler transform	last column of sorted rotations; FM-index	Burrows–Wheeler
Burrows–Wheeler transform, FM-index	compression and pattern counting on a suffix-sorted string	Burrows-Wheeler
Buss kernel	vertex cover kernel with at most k² edges	Complexity Theory

C

Name	What it does	Note
Carathéodory’s theorem	a point in the convex hull of $S\subset {\mathbb{R}}^d$ is in the hull of at most $d+1$ points of $S$	Convex Hull
Cantor–Zassenhaus algorithm	randomised factorisation over finite fields	Polynomial Factorization
Cantor–Zassenhaus	randomized factorization of polynomials over ${\mathbb{F}}_p$	Polynomial Factorization
Carmichael numbers, Carmichael λ	Fermat pseudoprimes to every base; the exponent of $(\mathbb{Z}/n{)}^{\ast }$	Primality Testing and Factorization
Cassini’s identity	$F_{n-1}{F}_{n+1}-F_n^2=(-1{)}^n$	Number Theory Miscellany
Catalan numbers	brackets, trees, triangulations, Dyck paths	Catalan and Lattice Paths
Cauchy–Binet	determinant of a product of rectangular matrices	Matrix-Tree Theorem
Cauchy–Schwarz	$(\sum a_i{b}_i{)}^2\le \sum a_i^2\sum b_i^2$	Graph Basics and Modeling
Cayley’s formula	n^(n-2) labelled trees, rooted forests k n^(n-k-1)	Counting Graphs and Trees
Cayley’s formula, Prüfer code	$n^{n-2}$ labelled trees, tree $\leftrightarrow$ sequence bijection	Prüfer Codes
Cayley–Hamilton theorem	a matrix satisfies its characteristic polynomial; A^k via x^k mod chi	Characteristic Polynomial
Cayley–Hamilton	a matrix satisfies its characteristic polynomial	Characteristic Polynomial
CDQ divide and conquer	offline 3D dominance / dynamic problems	CDQ
Centroid decomposition	all-paths problems on trees in $O(n\log n)$	Centroid Decomposition
Chan’s algorithm	output-sensitive convex hull in $O(n\log h)$	Convex Hull
Chazelle	linear-time polygon triangulation; soft-heap MST in $O(m\alpha )$	Theoretical Algorithms Catalog
Chebyshev distance	$\max (|dx|,|dy|)$; rotate 45° to turn it into Manhattan	Attacking a Problem
Chen–Fox–Lyndon theorem	unique factorization of a string into non-increasing Lyndon words	Lyndon Words and Minimal Rotation
Chernoff–Hoeffding bounds	exponential tail bounds for sums of independent variables	Probability and Expectation
Chinese remainder theorem, Garner	combine congruences	CRT
Chirp-z transform	evaluation at a geometric progression / DFT of any length	Convolution Variants
Christofides	3/2-approximation for metric TSP: MST + min matching on odd vertices + Euler tour	Approximation Algorithms
Chtholly tree (ODT)	assign-heavy interval maps on random data	Chtholly Tree
Chu–Liu–Edmonds	minimum arborescence (directed MST)	Directed MST
Church–Turing thesis	every effective procedure is a Turing machine	Complexity Theory and NP-Hardness
Cipolla, Tonelli–Shanks	modular square roots	Modular Square Roots
Cocke–Younger–Kasami (CYK)	$O(n^3)$ context-free parsing by interval DP	Interval DP
Coffman–Graham	two-processor precedence scheduling / layered drawing	DAGs and Topological Sort
Colon and fusion principles	reduce green Hackenbush on any graph to a number	Hackenbush
Color coding (Alon–Yuster–Zwick)	k-vertex paths in O((2e)^k m) expected	Randomized Search
Commentz-Walter	multi-pattern Boyer–Moore over a reversed trie	Theoretical Algorithms Catalog
Convex hull trick, Li Chao tree	min / max of lines queries, DP speedups	Convex Hull Trick
Conway’s surreal numbers	values of partizan games	Hackenbush and Partizan Games
Cook–Levin theorem	SAT is NP-complete	Complexity Theory and NP-Hardness
Cooley–Tukey FFT	convolution in $O(n\log n)$	FFT
Cooper–Harvey–Kennedy	simple iterative dominator algorithm	Dominator Tree
Coppersmith–Winograd	$O(n^{2.376})$ matrix multiplication	Theoretical Algorithms Catalog
Cops and robber (dismantlable graphs)	one cop wins iff corners can be deleted down to one vertex	Games on Graphs
Count-Min sketch	approximate frequency counts in small memory	Fast Set and Integer Structures
Count–Min sketch	frequency estimates with additive error εn	Sampling and Streaming
Courcelle’s theorem	MSO properties are linear-time on bounded treewidth	Complexity Theory and NP-Hardness
Cover’s switching strategy	randomized threshold that beats $\frac{1}{2}$ in the two-envelope game	Two Envelopes
Cramer’s rule	$x_i=\det A_i/\det A$	Determinants and Permanents
Crochemore–Perrin (Two-Way)	$O(n)$ time, $O(1)$ space string matching (glibc memmem)	Theoretical Algorithms Catalog
Cycle lemma	exactly k good rotations of a sequence with steps at most 1 and sum k	Catalan and Lattice Paths

D

Name	What it does	Note
Damerau–Levenshtein	edit distance with adjacent transpositions	LIS, LCS and Edit Distance
Dancing links (Algorithm X)	exact cover search	Exact Cover
de Bruijn graph / sequence	cyclic sequence containing every length-$k$ word once	Euler Tours
de Fraysseix–Rosenstiehl	left-right planarity test	Special Graph Classes
Delaunay / Voronoi	triangulation and nearest-site diagrams	Delaunay and Voronoi
Dial’s algorithm	Dijkstra with buckets for small integer weights	Shortest Paths
Dijkstra	single-source shortest paths, non-negative weights	Shortest Paths
Dilworth, Mirsky	chain covers vs antichains	Bipartite Matching
Dinic	max flow by blocking flows	Max Flow
Dinkelbach’s iteration	fractional programming by repeated parametric solves	Binary Search
Dinur–Steurer	$(1-\epsilon )\ln n$ hardness of set cover	Approximation Algorithms
Divide and conquer DP optimization	monotone optimum, $O(kn\log n)$	D&C Optimization
Dobkin–Kirkpatrick	hierarchical convex polyhedron for $O(\log n)$ queries	Point Location and Point Counting
Dominator tree (Lengauer–Tarjan)	immediate dominators in flow graphs	Dominator Tree
Downey–Fellows	parameterized complexity, W-hierarchy	Complexity Theory and NP-Hardness
Dreyfus–Wagner	Steiner tree DP in $O(3^{k}n+2^{k}m\log m)$	Steiner Tree
DSU on tree (sack)	offline subtree queries in $O(n\log n)$	Small to Large
Du’s sieve, Min_25 sieve	prefix sums of multiplicative functions in sublinear time	Sublinear Sieves
Dubins–Spanier moving knife	proportional cake cutting with $n-1$ cuts	Cake Cutting
Durand–Kerner	simultaneous iteration for all polynomial roots	Root Finding and Integration
Duval	Lyndon factorization in $O(n)$	Lyndon Words
Duval’s algorithm	Lyndon factorisation in O(n)	Lyndon Words

E

Name	What it does	Note
Edmonds’ arborescence (Chu–Liu)	minimum directed spanning tree	Directed MST
Erdős–Gallai theorem	which degree sequences are graphical, via a partial-sum condition	Special Graph Classes
Edmonds–Karp	max flow by BFS augmenting paths	Max Flow
Eertree	palindromic tree: one node per distinct palindrome	Eertree
Eertree (palindromic tree)	all distinct palindromes online	Eertree
Eisenstein’s criterion	a sufficient condition for irreducibility over $\mathbb{Q}$	Polynomial Factorization
Eppstein’s algorithm	$k$ shortest walks in $O(m+n\log n+k\log k)$	K Shortest and Disjoint Paths
Eratosthenes	primes up to $n$ in $O(n\log \log n)$	Sieves
Erdős–Szekeres theorem	$rs+1$ distinct numbers contain an increasing run of $r+1$ or a decreasing one of $s+1$	Pigeonhole Puzzles
Eswaran–Tarjan	minimum edges to make a digraph strongly connected: $\max (\#\text{sources},\#\text{sinks})$	SCC and 2-SAT
Euclid’s formula (Pythagorean triples)	all primitive triples as (m² − k², 2mk, m² + k²)	Number Theory Miscellany
Euclid–Euler theorem	even perfect numbers are $2^{p-1}(2^p-1)$	Primality Testing and Factorization
Euler transform	counting multisets / sets from object counts via exp	Counting with Power Series
Euler’s formula (planar graphs)	$V-E+F=2\cdot \text{components}$ for a graph embedded in the plane	Planar Faces
Euler’s theorem, Fermat’s little theorem	$a^{\phi (m)}\equiv 1$	Modular Arithmetic
Euler tour tree	link / cut with subtree aggregates	Euler Tour Tree
Even–Paz	proportional cake cutting with $O(n\log n)$ queries by divide and conquer	Cake Cutting
Extended Euclid	Bézout coefficients, inverses	GCD and Extended Euclid

F

Name	What it does	Note
Faddeev–LeVerrier algorithm	characteristic polynomial and inverse from traces	Characteristic Polynomial
Fagin’s theorem	NP = existential second-order logic	Complexity Theory
Farach-Colton–Bender	$O(n)$ / $O(1)$ RMQ	RMQ
Farey sequence next term	O(1) step to the next reduced fraction with denominator ≤ n	Big Integers and Fractions
Farey sequence	reduced fractions with bounded denominator, mediant neighbours	Continued Fractions and Pell Equations
Feller’s weak law (St. Petersburg)	$n$ St. Petersburg games pay about $n{\log }_{2}n$	St. Petersburg Paradox
Fenwick tree (BIT)	prefix sums with point updates	Fenwick Tree
Fine–Wilf periodicity lemma	periods p, q with $|s|\ge p+q-\gcd$ give period $\gcd$	String Basics
First Fit Decreasing	bin packing within 11/9 OPT + 6/9	Approximation Algorithms
Fisher–Yates shuffle	uniform random permutation in $O(n)$	Randomized Algorithms
FKM algorithm	de Bruijn sequences from Lyndon words	Lyndon Words
Floyd’s cycle finding	tortoise and hare	Functional Graphs
Floyd’s sampling algorithm	k distinct uniform values from [0, n) in O(k)	Sampling and Streaming
Floyd–Warshall	all-pairs shortest paths $O(n^3)$	Shortest Paths
FM-index	backward search pattern counting on the BWT	Burrows–Wheeler
Ford–Fulkerson	augmenting paths, max-flow min-cut	Max Flow
Ford–Johnson (merge insertion)	sorting with near-minimum comparisons	Sorting, Selection and Inversions
Fortune’s algorithm	Voronoi diagram by a sweep line in $O(n\log n)$	Delaunay and Voronoi
Frame–Stewart	Tower of Hanoi with 4+ pegs	Tower of Hanoi
Fredman–Tarjan	Fibonacci heaps; Dijkstra in $O(m+n\log n)$	Heaps
Fredman–Willard	fusion trees: predecessor in $O({\log }_{w}n)$	Fast Set and Integer Structures
Fredricksen–Kessler–Maiorana	de Bruijn sequence by concatenating Lyndon words	Lyndon Words and Minimal Rotation
Freivalds’ algorithm	check $AB=C$ in $O(n^2)$ per random trial	Randomized Algorithms
Frobenius number (Chicken McNugget)	largest non-representable amount $ab-a-b$	Linear Congruences and CRT
Fuss–Catalan numbers	k-ary trees, generalised ballot	Catalan and Lattice Paths
Fürer’s algorithm	integer multiplication in $n\log n{2}^{O({\log }^{\ast }n)}$	Theoretical Algorithms Catalog

G

Name	What it does	Note
Gabow’s algorithm	path-based SCC with two stacks	SCC and 2-SAT
Gabow–Edmonds	efficient weighted general matching	Theoretical Algorithms Catalog
Gabow–Tarjan	cost-scaling assignment and matching	Assignment Problem
Gale’s Hex theorem	a full Hex board has exactly one winner (boundary-walk proof)	Chomp and Hex
Gale–Ryser	which degree pairs are realisable by a bipartite graph	Special Graph Classes
Gale–Shapley	stable marriage	Stable Matching
Galil–Seiferas	linear-time string matching with $O(1)$ extra space	Theoretical Algorithms Catalog
Gallai–Edmonds decomposition	structure of maximum matchings in general graphs	General Matching
Garner’s algorithm	mixed-radix CRT reconstruction (three-prime NTT)	NTT
Garsia–Wachs	optimal alphabetic binary tree in $O(n\log n)$	Knuth-Yao Optimization
Gaussian elimination, Bareiss	linear systems, rank, determinant	Gaussian Elimination
Gauss–Jordan elimination	reduced row echelon form, inverse, rank	Gaussian Elimination, Rank and Inverse
Gauss–Legendre quadrature	exact for polynomials of degree $2n-1$	Root Finding and Integration
Goemans–Williamson	0.878-approximation of max-cut via an SDP	Approximation Algorithms
Goldberg–Tarjan	push–relabel max flow; cost scaling	Maximum Flow
Golomb–Dickman constant	expected longest cycle of a random permutation $\approx 0.624n$	100 Prisoners
Gomory’s domino theorem	a chessboard minus one white and one black square is domino-tileable	Mutilated Chessboard
Gomory–Hu tree	all-pairs min cuts with $n-1$ flows	Gomory-Hu Tree
Gonzalez farthest-point clustering	2-approximation for k-center	Approximation Algorithms
Good–Thomas (prime-factor FFT)	DFT of length $n_1{n}_2$, coprime factors, no twiddles	Theoretical Algorithms Catalog
Graeffe iteration	root squaring for polynomials and for Bostan–Mori	Composition and Taylor Shift
Graham scan	convex hull	Convex Hull
Gray code	adjacent subsets differ in one bit	Gray Code
Green’s theorem	area of a region from a boundary integral (circle union)	Circle Union and Angular Sweep
Greene’s theorem	RSK shape = sizes of $k$ disjoint increasing subsequences	Young Tableaux and RSK
Grover’s algorithm	quantum search in $O(\sqrt{N})$	Complexity Theory and NP-Hardness
Guibas–Stolfi	divide-and-conquer Delaunay with the quad-edge structure	Delaunay and Voronoi
Guy–Smith periodicity theorem	a row game whose Grundy values repeat on a finite window is periodic forever	Sprague–Grundy

H

Name	What it does	Note
Hadamard bound	$|\det A|\le \prod \Vert a_i\Vert$	Determinants and Permanents
Half-GCD	polynomial gcd in O(n log^2 n)	GCD and Resultant
Helly’s theorem	if every $d+1$ of a family of convex sets in ${\mathbb{R}}^d$ intersect, the whole family intersects; underlies LP-type algorithms	Linear Programming
Hall, König, Tutte	matching existence and min-max theorems	Bipartite Matching
Hall’s theorem / condition	a perfect matching of $L$ exists iff $|N(S)|\ge |S|$ for every $S$	Bipartite Matching
Hamming distance	number of differing positions (popcount of XOR)	Bitset
Handshake lemma	$\sum \mathrm{deg}=2m$; the number of odd vertices is even	Graph Basics and Modeling
Han–Thorup	integer sorting in $O(n\sqrt{\log \log n})$	Theoretical Algorithms Catalog
Harel–Tarjan	first $O(n)$ / $O(1)$ LCA	Theoretical Algorithms Catalog
Harmonic numbers	$H_n=\ln n+\gamma +O(1/n)$, the harmonic-lemma bound	Harmonic Lemma and Floor Sums
Hasse’s theorem	$|\#E({\mathbb{F}}_p)-p-1|\le 2\sqrt{p}$	Theoretical Algorithms Catalog
Havel–Hakimi	test and construct a graph with a given degree sequence	Special Graph Classes
Heavy-light decomposition	path queries in $O({\log }^{2}n)$	HLD
Held–Karp	TSP / Hamiltonian path DP in $O(2^n{n}^2)$	Hamiltonian Paths and TSP
Heron’s formula	triangle area from its side lengths	Polygons
Hessenberg method	characteristic polynomial in $O(n^3)$	Characteristic Polynomial
Hessenberg reduction	characteristic polynomial in O(n^3)	Characteristic Polynomial
Hierholzer	Euler tours in $O(m)$	Euler Tours
Hirschberg	LCS / alignment in linear space	Sequence DP
Hoeffding’s lemma	tail bounds for bounded independent variables	Probability and Expectation
Hollow heap	simple heap with Fibonacci-heap bounds	Heaps
Hopcroft–Karp	bipartite matching $O(E\sqrt{V})$	Bipartite Matching
Hopcroft–Tarjan	linear DFS: biconnectivity, triconnectivity, planarity	Special Graph Classes
Horner’s rule	evaluate a polynomial with $n$ multiplications	Root Finding and Integration
Horspool’s algorithm	simplified Boyer–Moore with one shift table	Other Matching
Hungarian (Kuhn–Munkres)	assignment problem $O(n^3)$	Assignment Problem
Hunt–Szymanski	LCS in $O((r+n)\log n)$ with $r$ matching pairs	LIS, LCS and Edit Distance
Hu–Shing	$O(n\log n)$ matrix-chain multiplication	Interval DP
Hu–Tucker	optimal alphabetic code tree	Knuth-Yao Optimization
HyperLogLog	distinct count with relative error ≈ 1.04/√m	Sampling and Streaming

I

Name	What it does	Note
Irving’s algorithm	stable roommates	Stable Matching
Itai–Papadimitriou–Szwarcfiter	Hamiltonian paths in grid graphs	Hamiltonian Paths and TSP

J

Name	What it does	Note
Jensen’s inequality	for convex $f$, $f(\text{mean of }{a}_i)\le$ mean of $f(a_i)$ (reverse for concave)	🐬 Formula
Johnson	all-pairs shortest paths with reweighting	Shortest Paths
Jonker–Volgenant	fast shortest-augmenting-path assignment	Assignment Problem
Josephus problem	$J(n,k)$ survivor recurrence and the $O(k\log n)$ jump	Classic Puzzles

K

Name	What it does	Note
Kac’s lemma	expected return time $=1/{\pi }_i$ in a Markov chain	Probability and Expectation
Kadane	maximum subarray	Classic Array Problems
Kahn’s algorithm	BFS topological sort by in-degree	DAGs and Topological Sort
Kaltofen–Shoup	subquadratic distinct-degree factorization	Polynomial Factorization
Karatsuba multiplication	3 half-size products, O(n^1.585)	Fast Fourier Transform
Karatsuba	multiplication in $O(n^{1.585})$	FFT
Karger, Karger–Stein	randomized global min cut	Global Min Cut
Karger–Klein–Tarjan	randomized linear-time MST	Theoretical Algorithms Catalog
Kariv–Hakimi	absolute 1-center of a graph	Minimum Spanning Trees
Karlin–Klein–Oveis Gharan	$(1.5-\epsilon )$-approximation for metric TSP	Approximation Algorithms
Karmarkar–Karp (differencing)	largest-differencing heuristic for number partitioning	Scheduling and Partitioning
Karp’s minimum mean cycle	minimum mean-weight cycle in $O(nm)$	Shortest Path Techniques
Karp–Miller–Rosenberg naming	prefix doubling: O(1) equality of substrings	Suffix Array
Karp–Miller–Rosenberg	prefix doubling for suffix arrays / naming	Suffix Array and LCP
Kasai	LCP array from a suffix array in $O(n)$	Suffix Array
Kasai’s algorithm	LCP array from the suffix array in O(n)	Suffix Array
Kasteleyn’s formula	domino tilings via a Pfaffian	Broken Profile DP
Kawarabayashi–Thorup	deterministic near-linear min cut in simple graphs	Global Minimum Cut
Kayles	remove 1 or 2 adjacent pins; Grundy period 12 from 71	Sprague–Grundy
King–Rao–Tarjan	deterministic max flow in $O(nm)$ for dense graphs	Theoretical Algorithms Catalog
Kinoshita–Li composition	f(g(x)) mod x^n in O(n log^2 n) via power projection	Composition and Taylor Shift
Kirkman triple system	resolvable Steiner triple system; exists iff $v\equiv 3(\mathrm{mod}6)$	Kirkman’s Schoolgirls
Kirkpatrick–Seidel	”ultimate” convex hull in $O(n\log h)$	Convex Hull
Kitamasa’s method	n-th term of a linear recurrence in O(k^2 log n)	Linear Recurrences
Kleitman–Kwiatkowski bound	a Fitch Cheney trick with $n$ cards exists iff the deck has at most $n!+n-1$ cards	Fitch Cheney Trick
KMP (prefix function)	pattern matching, borders, periods	Prefix Function and Z
Knuth–Morris–Pratt algorithm	linear-time matching with the prefix function	Prefix Function and Z
Knuth–Morris–Pratt	linear string matching with the prefix function	Prefix Function and Z-Function
Knuth–Plass	optimal line breaking (monotone DP)	Monotone Queue, 1D1D and SMAWK
Knuth–Yao optimization	interval DP in $O(n^2)$	Knuth Optimization
Knuth–Yao speedup	$O(n^2)$ interval DP under the quadrangle inequality	Knuth-Yao Optimization
Kummer’s theorem	p-adic valuation of a binomial = number of carries	Binomial Identities
König–Egerváry, König–Ore	bipartite max matching = min vertex cover; deficiency formula	Bipartite Matching
Kosaraju, Tarjan SCC	strongly connected components	SCC and 2-SAT
Kruskal	MST with a DSU	MST
Kruskal reconstruction tree	bottleneck paths, reachability under thresholds	Kruskal Reconstruction Tree
Kuhn	bipartite matching by augmenting DFS	Bipartite Matching
Kuratowski’s theorem	planar iff no $K_5$ or $K_{3,3}$ subdivision	Special Graph Classes

L

Name	What it does	Note
Lagrange interpolation	polynomial from point values	Interpolation
Lagrange inversion	coefficients of compositional inverses	Generating Functions
Lanczos algorithm	Krylov tridiagonalisation for symmetric eigenproblems	Sparse and Structured Matrices
Landau–Vishkin	$k$-differences matching in $O(kn)$	LIS, LCS and Edit Distance
Larmore–Schieber	concave 1D/1D DP in linear time	Monotone Queue, 1D1D and SMAWK
Lasker’s Nim	remove or split a heap; Grundy values swap within blocks of 4	Sprague–Grundy
Legendre’s formula, Kummer, Lucas	prime powers in factorials and binomials	Factorials mod p
Lehmer code	permutation $\leftrightarrow$ factorial number system, rank and unrank	Counting Fundamentals
Lempel–Even–Cederbaum	st-numbering-based planarity test	Special Graph Classes
Lempel–Ziv	LZ77/LZ78 factorization and compression	Runs and Periodicity
Lenstra ECM	elliptic-curve factorization	Theoretical Algorithms Catalog
Lenstra–Lenstra–Lovász (LLL)	lattice basis reduction	Polynomial Factorization
Lenstra–Shmoys–Tardos	2-approximation for unrelated machine scheduling	Scheduling and Partitioning
Levenshtein distance	edit distance DP	LIS, LCS and Edit Distance
Lichtenberg–Thorup (Holm–de Lichtenberg–Thorup)	fully dynamic connectivity in $O({\log }^{2}n)$ amortized	Dynamic Connectivity
Lindström–Gessel–Viennot lemma	non-intersecting lattice paths as a determinant	Determinants
Lindström–Gessel–Viennot	non-intersecting lattice paths as a determinant	Determinants and Permanents
Linear conflict heuristic	Manhattan distance plus 2 per tile that must leave its line; admissible for sliding puzzles	Fifteen Puzzle
Link-cut tree	dynamic trees with path aggregates	Link-Cut Tree
Lin–Kernighan	variable-depth local search for TSP	Hamiltonian Paths and TSP
Lipton–Tarjan	planar separator theorem, $O(\sqrt{n})$ separators	Special Graph Classes
LPT scheduling	longest processing time first, (4/3 − 1/(3m))-approximate makespan	Approximation Algorithms
Lucas–Lehmer	primality test for Mersenne numbers	Primality Testing and Factorization
Lucy_Hedgehog’s algorithm	$\pi (n)$ and prime sums in $O(n^{3/4})$	Sublinear Sieves and Prime Counting
LUX method (Conway)	magic squares of order $n\equiv 2(\mathrm{mod}4)$	Magic Squares

M

Name	What it does	Note
MacNeish construction	Kronecker products of orthogonal Latin squares	Latin Squares
Main–Lorentz algorithm	all runs / tandem repeats in O(n log n)	Runs and Periodicity
Main–Lorentz	all tandem repeats in $O(n\log n)$	Runs and Periodicity
Malhotra–Kumar–Maheshwari (MPM)	$O(V^3)$ blocking-flow max flow	Maximum Flow
Mantel’s theorem	a triangle-free graph on $n$ vertices has at most $\lfloor n^2/4\rfloor$ edges (the $r=2$ case of Turán)	Constructive Algorithms
Manacher	all palindromic radii in $O(n)$	Palindromes
Manacher’s algorithm	all maximal palindromes in O(n)	Palindromes
Manber–Myers	$O(n\log n)$ suffix array by doubling	Suffix Array and LCP
Manhattan distance	$|dx|+|dy|$; MST and farthest pair via $x\pm y$	Attacking a Problem
Matrix-tree theorem (Kirchhoff)	counting spanning trees	Matrix-Tree Theorem
McCreight	linear-time suffix tree	Theoretical Algorithms Catalog
Megiddo’s algorithm	2D/3D linear programming in $O(n)$ (prune and search)	Linear Programming
Meissel–Lehmer	$\pi (n)$ in about $O(n^{2/3})$	Sublinear Sieves and Prime Counting
Moore’s Nim	remove from up to k heaps; losing iff every bit column sums to 0 mod k+1	Combinatorial Games and Nim
Myers’ bit-vector algorithm	edit distance in O(n m / w)	Other Matching
Ménage problem	seating couples alternately with no partners adjacent	Inclusion-Exclusion and Derangements
Menger’s theorem	max disjoint paths = min cut	Minimum Cut
Mersenne numbers	$2^p-1$, Lucas–Lehmer test	Primality Testing and Factorization
Mertens’ theorems	${\sum }_{p\le n}1/p=\ln \ln n+M+o(1)$	Primes and Sieves
Metropolis criterion	acceptance rule in simulated annealing	Heuristic Optimization
Micali–Vazirani	general matching in $O(E\sqrt{V})$	General Matching
Miller–Rabin	deterministic 64-bit primality	Primality and Factorization
Miller–Reif	parallel tree contraction (rake and compress)	Top Trees
Minkowski sum	sum of convex polygons in $O(n+m)$	Minkowski Sum
Misra–Gries	heavy hitters, more than $n/k$ occurrences, in $O(k)$ space	Classic Array Problems
Mo’s algorithm (and variants)	offline range queries in $O(n\sqrt{q})$	Mo’s Algorithm
Möbius inversion	inclusion–exclusion over divisors	Arithmetic Functions
Monge condition	$A[i][j]+A[i^{\prime }][j^{\prime }]\le A[i][j^{\prime }]+A[i^{\prime }][j]$, which gives monotone argmins	Monotone Queue, 1D1D and SMAWK
Montgomery multiplication	division-free modular products	Barrett and Montgomery
Moon–Moser	a graph has at most $3^{n/3}$ maximal cliques	Maximum Clique and Independent Set
Moore–Hodgson	minimise the number of late jobs	Scheduling and Partitioning
Moore–Penrose pseudoinverse	least-squares solutions	Root Finding and Integration
Mucha–Sankowski	matching via Gaussian elimination in $O(n^{\omega })$	General Matching
Mycielski construction	triangle-free graphs of any chromatic number	Constructive Algorithms

N

Name	What it does	Note
Nagamochi–Ibaraki	sparse $k$-connectivity certificates	Global Min Cut
Nash-Williams–Tutte	$k$ edge-disjoint spanning trees; arboricity formula	Matroids
Needleman–Wunsch	global sequence alignment	LIS, LCS and Edit Distance
Nemhauser–Trotter	half-integral vertex cover LP, $2k$ kernel	Complexity Theory and NP-Hardness
Nemhauser–Wolsey–Fisher	greedy gives $(1-1/e)$ for monotone submodular maximisation	Approximation Algorithms
Network simplex	fast practical min-cost flow	Min-Cost Flow
Newton iteration (power series)	inverse, log, exp, sqrt of a series in $O(n\log n)$	Power Series Operations
Newton’s identities	power sums $\leftrightarrow$ elementary symmetric polynomials	Characteristic Polynomial
Newton’s method (power series)	inverse, log, exp, sqrt of series	Power Series
Newton–Raphson	quadratically convergent root finding	Root Finding and Integration
Newton–Schulz iteration	matrix inverse with only multiplications, quadratic convergence	Root Finding and Integration
Newton–Schulz	iterative matrix inverse	Root Finding and Integration
Non-adjacent form (NAF)	signed binary digits with no two adjacent non-zeros, minimal weight	Number Theory Miscellany
NTT	exact convolution modulo primes	NTT
Number-theoretic transform	exact FFT over Z_p with p = c 2^k + 1	NTT

O

Name	What it does	Note
Ore’s theorem	$\mathrm{deg}u+\mathrm{deg}v\ge n$ for non-adjacent $u,v$ implies Hamiltonian	Hamiltonian Paths and TSP
Orlin’s algorithm	strongly polynomial min-cost flow; $O(nm)$ max flow	Theoretical Algorithms Catalog
Otter’s dissimilarity theorem	unlabelled free trees from rooted trees	Counting Graphs and Trees
Otter’s formula	counting unlabelled trees	Tree Isomorphism and Prüfer Codes

P

Name	What it does	Note
Pairing heap	simple meldable heap, fast in practice	Heaps
Papadimitriou’s random walk	2-SAT in O(n²) expected flips	Randomized Search
Parallel binary search	many monotone searches at once	Parallel Binary Search
Pascal’s rule, Pascal’s triangle	$\left(\genfrac{}{}{0ex}{}{n}{k}\right)=\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)+\left(\genfrac{}{}{0ex}{}{n-1}{k}\right)$	Counting Fundamentals
Pentagonal number theorem	partition numbers in O(n sqrt n); Franklin’s involution	Stirling, Bell and Partitions
Pisano period	period of Fibonacci numbers modulo m	Number Theory Miscellany
Power tower (generalized Euler theorem)	a^x ≡ a^(x mod φ(m) + φ(m)) mod m for x ≥ φ(m)	Number Theory Miscellany
Principal variation search (NegaScout)	null-window alpha-beta with re-search	Game Search
Proof-number search	best-first proof of a forced win with proof / disproof numbers	Game Search
Pépin’s test	primality of Fermat numbers	Theoretical Algorithms Catalog
Persistent segment tree	versioned arrays, $k$-th smallest in a range	Persistent Segment Trees
Pettie–Ramachandran	optimal (decision-tree-optimal) MST algorithm	Theoretical Algorithms Catalog
Picard–Queyranne	all minimum $s$-$t$ cuts from a residual graph	Minimum Cut
Pick’s theorem	$A=I+B/2-1$ for lattice polygons	Polygons
Pigeonhole principle	$n+1$ objects in $n$ boxes; prefix sums mod $n$	Invariants, Parity and Extremal Arguments
Pohlig–Hellman	discrete log in a group of smooth order	Primitive Roots and Discrete Log
Pollard’s $p-1$	factor $n$ when $p-1$ is smooth	Primitive Roots and Discrete Log
Pollard’s rho (Brent)	64-bit factorization in $\tilde{O}(n^{1/4})$	Primality and Factorization
Prim	MST in $O(m\log n)$ or $O(n^2)$	MST
Push–relabel (HLPP)	max flow for dense / hard graphs	Push-Relabel

Q

Name	What it does	Note
q-Lucas theorem	q-binomials modulo p when q has small order	Stirling, Bell and Partitions
Quadratic sieve	subexponential factorization	Theoretical Algorithms Catalog

R

Name	What it does	Note
Radon’s theorem	any $d+2$ points in ${\mathbb{R}}^d$ split into two sets whose convex hulls intersect	Linear Programming
Rabin’s irreducibility test	irreducibility over F_p via x^(p^n) - x	Polynomial Factorization
Rabin–Karp algorithm	pattern matching with rolling hashes	String Hashing
Rabin–Karp	rolling-hash matching	String Hashing
Rabin–Vazirani	randomized matching via the Tutte matrix	General Matching
Rader’s algorithm	prime-length DFT via cyclic convolution	Convolution Variants
Rado–Edmonds	greedy is optimal exactly on matroids	Matroids
Raghavan–Thompson	randomized rounding with Chernoff bounds	Approximation Algorithms
Ramsey’s theorem	$R(3,3)=6$: any 2-colouring of $K_6$‘s edges has a monochromatic triangle, and generally $R(k,k)$ is finite	Party Problem
Randomized rounding (Raghavan–Thompson)	round an LP solution by treating values as probabilities	Approximation Algorithms
Rearrangement inequality	similarly ordered sequences maximise $\sum a_i{b}_i$	Greedy and Exchange Arguments
Reeds–Sloane algorithm	shortest linear recurrence modulo a composite	Linear Recurrences
Reed–Solomon	polynomial evaluation codes	Polynomial Factorization
Reeds–Sloane	Berlekamp–Massey modulo composite $m$	Linear Recurrences
Reif	planar min cut / max flow via shortest paths in the dual	Theoretical Algorithms Catalog
Relaxed multiplication	online convolution in O(n log^2 n)	Online Convolution
Reservoir sampling (Algorithm R, Algorithm L)	uniform k-sample of a stream in O(k) memory	Sampling and Streaming
Retrograde analysis	win / loss / draw of a cyclic game graph backwards from terminal positions	Loopy Games
Robbins’ theorem	strongly orientable iff 2-edge-connected	Bridges and Biconnectivity
Robinson’s recurrence	counting labelled DAGs by inclusion–exclusion over sources	Counting Graphs and Trees
Rotating calipers	diameter, widths, antipodal pairs	Rotating Calipers
RSK correspondence, hook length formula	Young tableaux counting	Young Tableaux and RSK
Rule of three (peg solitaire)	diagonal 3-colouring parity invariant of peg solitaire	Peg Solitaire
Runs theorem	a string has fewer than $n$ maximal repetitions	Runs and Periodicity
Ryser’s formula	permanent in $O(2^{n}n)$	Determinants and Permanents

S

Name	What it does	Note
SA-IS	suffix array in $O(n)$	Suffix Array
Schieber–Vishkin	$O(1)$ LCA after $O(n)$ preprocessing	LCA
Schreier–Sims algorithm	order and membership of a permutation group	Burnside and Pólya
Schwartz–Zippel lemma	a non-zero degree-d polynomial vanishes at a random point with probability $\le d/|S|$	Hashing and Verification
Schönhage–Strassen	integer multiplication in $O(n\log n\log \log n)$	Theoretical Algorithms Catalog
Schreier–Sims	permutation group order and membership	Burnside and Pólya
Schroeppel–Shamir	meet in the middle with $O(2^{n/4})$ memory	Meet in the Middle
Schwartz–Zippel	a random point detects a nonzero polynomial with probability $\ge 1-d/|S|$	Randomized Algorithms
Schwenk’s theorem	which boards admit a closed knight’s tour	Backtracking and Pruning
Schöning’s algorithm	random-walk 3-SAT in O((4/3)^n poly n)	Randomized Search
Secretary problem	optimal stopping, skip $n/e$, success $1/e$	Secretary Problem
Segment tree beats (Ji driver)	range chmin / chmax with sums	Segment Tree Beats
Seidel’s algorithm	randomized LP in fixed dimension, expected $O(n)$	Linear Programming
Seidel’s LP	randomized incremental LP in fixed dimension, expected O(d! n)	Linear Programming
Selfridge–Conway	envy-free cake cutting for 3 people with at most 5 cuts	Cake Cutting
Shamos–Hoey	detect any segment intersection in $O(n\log n)$	Sweep Line and Segment Intersections
Sharir–Welzl	LP-type problems, randomized	Linear Programming
Sherman–Morrison formula	inverse after a rank-one update in O(n^2)	Sparse and Structured Matrices
Sherman–Morrison	rank-1 update of a matrix inverse	Sparse and Structured Matrices
Shoelace formula	polygon area from its vertex coordinates	Points, Vectors and Orientation
Siamese method	odd-order magic squares	Constructive Algorithms
Simpson’s rule	adaptive numerical integration	Root Finding and Integration
Simulated annealing	Metropolis acceptance with a cooling schedule	Heuristic Optimization
Skew heap, leftist heap	meldable heaps in $O(\log n)$	Heaps
Skolem construction	Steiner triple system on $v\equiv 1(\mathrm{mod}6)$ points from a half-idempotent quasigroup	Kirkman’s Schoolgirls
Sleator–Tarjan	link-cut trees; splay trees	Link-Cut Tree
Slope trick	DP over convex piecewise-linear functions	Slope Trick
SMAWK	row minima of totally monotone matrices in $O(n)$	Monotone Optimizations
Smith’s rule	minimise weighted completion time: sort by $p_i/w_i$	Scheduling and Partitioning
Smith–Waterman	local sequence alignment	LIS, LCS and Edit Distance
SOS DP (zeta / Möbius transform)	sums over subsets in $O(n{2}^n)$	Submasks and SOS DP
Sparse table	$O(1)$ idempotent range queries	Sparse Table
Sperner’s theorem	the largest antichain in $2^{[n]}$ has size $\left(\genfrac{}{}{0ex}{}{n}{\lfloor n/2\rfloor }\right)$	Modular Arithmetic
SPFA	Bellman–Ford with a queue	Shortest Paths
Splay tree	self-adjusting BST, amortized $O(\log n)$	Treaps and Balanced BSTs
Sprague–Grundy	impartial game sums	Sprague-Grundy
Staircase Nim	Nim on the odd-indexed steps	Combinatorial Games and Nim
Stanley sequence	greedy 3-AP-free sequence (base-3 digits)	Constructive Algorithms
Stern–Brocot simplest fraction	smallest-denominator fraction in an interval in O(log) via continued fractions	Big Integers and Fractions
Stern–Brocot tree	rationals, best approximations	Continued Fractions
Stirling numbers	cycles (first kind) and set partitions (second kind)	Stirling, Bell and Partition Numbers
Stirling’s approximation	$n!\approx \sqrt{2\pi n}(n/e{)}^n$	🐬 Formula
Stoer–Wagner	deterministic global min cut	Global Min Cut
Strassen’s algorithm	matrix product with 7 block multiplications, O(n^2.807)	Matrices and Matrix Power
Strategy stealing	the first player wins (Chomp, Hex) without an explicit strategy	Chomp and Hex
Subproduct tree	multipoint evaluation and interpolation in O(n log^2 n)	Evaluation and Interpolation
Suffix automaton	all substrings in $O(n)$ states	Suffix Automaton
Surreal numbers	Conway’s numbers as game values	Hackenbush and Partizan Games
Sutherland–Hodgman	clip a polygon against a convex polygon	Polygons
Suurballe’s algorithm	$k$ edge-disjoint shortest paths of minimum total length	K Shortest and Disjoint Paths
Sweep line (Bentley–Ottmann)	segment intersections	Sweep Line
Swinnerton-Dyer polynomials	worst case for Zassenhaus factorization	Polynomial Factorization
Sylvester’s identity	determinant identity behind Bareiss elimination	Determinants and Permanents
Sylvester–Gallai	non-collinear points have an ordinary line	Invariants, Parity and Extremal Arguments

T

Name	What it does	Note
Tabu search	local search with a memory of forbidden moves	Heuristic Optimization
Tango tree	$O(\log \log n)$-competitive BST	Fast Set and Integer Structures
Tarjan bridges / articulation points	lowlink	Bridges and Biconnectivity
Tarjan offline LCA	LCA with a DSU	LCA
Tarjan–Vishkin	biconnected components via spanning-tree connectivity	Bridges and Biconnectivity
Tarjan–Werneck	self-adjusting top trees	Top Trees
Tarjan–Yannakakis	maximum cardinality search, chordality test	Special Graph Classes
Thomas algorithm	tridiagonal systems in O(n)	Sparse and Structured Matrices
Thue–Morse anti-hash	strings of length 2^11 collide under every polynomial hash mod 2^64	Hashing and Verification
Thue–Morse sequence	parity of popcount; breaks hashes mod $2^{64}$	String Hashing
Toom–Cook	$O(n^{1.465})$ split-into-3 multiplication	Fast Fourier Transform
Top tree	dynamic trees with path and subtree data	Top Trees
Touchard’s formula	ménage problem count via rook numbers on a cycle	Inclusion–Exclusion
Toussaint’s rotating calipers	width, diameter and bounding boxes of convex polygons	Rotating Calipers
Treap	randomized balanced BST, implicit keys	Treaps
Trygub numbers	big numbers with digits allowed to go negative, $O(\log )$ updates	Modular Arithmetic
Tsin’s algorithm	3-edge-connected components	Bridges and Biconnectivity
Turán’s theorem, Turán graph	max edges without a $K_{r+1}$	Constructive Algorithms
Tutte–Berge formula	max matching $={\min }_U\frac{n+|U|-\text{odd}(G-U)}{2}$	General Matching
Two-SAT	implication graph + SCC	SCC and 2-SAT

U

Name	What it does	Note
Ukkonen	suffix tree online	Suffix Tree
Ukkonen’s algorithm	online suffix tree construction	Suffix Tree

V

Name	What it does	Note
van Emde Boas tree	predecessor in $O(\log \log U)$	Fast Set and Integer Structures
Vandermonde’s identity	${\sum }_k\left(\genfrac{}{}{0ex}{}{m}{k}\right)\left(\genfrac{}{}{0ex}{}{n}{r-k}\right)=\left(\genfrac{}{}{0ex}{}{m+n}{r}\right)$	Binomial Identities
Vertex geography (Gallai–Edmonds)	first player wins iff every maximum matching covers the start	Games on Graphs
Vizing’s theorem	chromatic index is $\Delta$ or $\Delta +1$; constructive $\Delta +1$ edge-colouring by fan rotations	Graph Coloring

W

Name	What it does	Note
Walsh–Hadamard transform	xor / and / or convolutions	Bitwise Convolutions
Warnsdorff’s rule	knight’s tour heuristic: fewest onward moves first	Backtracking and Pruning
Wedderburn–Etherington numbers	unlabelled binary rooted trees	Tree Isomorphism and Prüfer Codes
Weiler–Atherton	clip general (non-convex) polygons	Polygons
Weiner’s algorithm	first linear-time suffix tree	Theoretical Algorithms Catalog
Weiszfeld’s iteration	geometric median	Minimum Enclosing Circle
Welzl	minimum enclosing circle in expected $O(n)$	Minimum Enclosing Circle
Wiedemann’s algorithm	sparse solve / determinant via Krylov sequence + Berlekamp–Massey	Sparse and Structured Matrices
Wilson’s algorithm	uniform spanning tree by loop-erased random walks	Matrix-Tree Theorem
Wilson’s sliding-puzzle theorem	on a 2-connected bipartite graph (not a cycle or ${\theta }_0$) sliding tokens realise exactly the even permutations	Fifteen Puzzle
Wilson’s theorem	$(p-1)!\equiv -1(\mathrm{mod}p)$	Factorials and Binomials mod p
Winding number	point in polygon for self-intersecting polygons	Polygons
Worpitzky’s identity	powers as sums of Eulerian numbers times binomials	Stirling, Bell and Partitions
Wu–Manber	hashed multi-pattern shift matching	Theoretical Algorithms Catalog
Wythoff’s game	losing positions $(\lfloor k\phi \rfloor ,\lfloor k{\phi }^2\rfloor )$	Sprague-Grundy

Y

Name	What it does	Note
Yao’s minimax principle	lower bounds for randomized algorithms	Complexity Theory and NP-Hardness
Yen’s algorithm	$k$ shortest simple paths	K Shortest and Disjoint Paths
Yun’s algorithm	square-free decomposition	Polynomial Factorization

Z

Name	What it does	Note
Z-algorithm	longest common prefix with every suffix in O(n)	Prefix Function and Z
Z-function	longest common prefix with every suffix	Prefix Function and Z
Zassenhaus	factor integer polynomials via Hensel lifting	Polynomial Factorization
Zeckendorf representation	unique sum of non-consecutive Fibonacci numbers, found greedily	Number Theory Miscellany
Zermelo’s theorem	every finite two-player perfect-information game is determined: one player has a forced win, or both can force at least a draw; backward induction (minimax) finds which	Game Search
Zeller / misc date and number tricks	see the formula list	🐬 Formula
Zobrist hashing	XOR of random keys per state component	Randomized Algorithms
Zsigmondy’s theorem	for coprime $a>b\ge 1$, $a^n-b^n$ has a prime factor dividing no earlier $a^k-b^k$, except a few small cases	—