Wasil Zafar

Noga Alon , Yossi Matias , and Mario Szegedy published "The Space Complexity of Approximating the Frequency Moments" in 1996 — the foundational paper of streaming algorithms, later earning its authors the Gödel Prize.

Stephen Cook published "The Complexity of Theorem-Proving Procedures" in 1971, proving that Boolean satisfiability (SAT) is NP-complete — the founding result of computational complexity theory.

Dénes Kőnig — already met in this series for König's theorem on bipartite matching ( Part 16 ) and König's theorem's role in perfect graphs ( Part 18 ) — also wrote the very first textbook on graph theory in 1936, and within it proved what is now called K…

Mechthild Stoer and Frank Wagner published "A Simple Min-Cut Algorithm" in 1997, providing a strikingly clean way to compute the global minimum cut of a weighted, undirected graph — the cheapest way to split the graph's vertices into two non-empty groups,…

Larry Page and Sergey Brin , then Stanford PhD students, described PageRank in a 1998 technical report, "The PageRank Citation Ranking: Bringing Order to the Web," and the same year in "The Anatomy of a Large-Scale Hypertextual Web Search Engine" — the pa…

David Karger introduced this randomized contraction algorithm in his 1993 Stanford PhD thesis and a related paper, showing — remarkably — that a purely random process could find the global minimum cut with high probability, in an algorithm dramatically si…

Václav Havel , a Czech mathematician, first proved this characterization in 1955.

Mathematical models in evolutionary biology — fitness landscapes, adaptive dynamics, evolutionary stable strategies (ESS), Lotka-Volterra models, coalescent theory, Price equation, diffusion models, evolutionary optimization, and computational simulations.

Graph theory's open problems are frequently far easier to state than the machinery needed to solve them — a running theme across this entire series, from the Four Color Theorem's century-long wait ( Part 13 ) to the still-unresolved gap between the best-k…

Arthur Cayley , the same mathematician whose 1889 tree-counting formula appeared in Part 11 , published "On the Mathematical Theory of Isomers" in 1874 — using trees to systematically count the possible structural arrangements of saturated hydrocarbon mol…

Franco Scarselli and colleagues introduced the foundational "Graph Neural Network Model" in a 2009 paper, formalizing how a neural network could operate directly on graph-structured input.

Psychologist Stanley Milgram 's 1967 "small world" experiment asked ordinary Americans to route a letter to a stranger using only acquaintance chains — the letters that arrived took a median of about six intermediaries, popularizing the phrase "six degrees

Vincent Blondel , Jean-Loup Guillaume , Renaud Lambiotte , and Etienne Lefebvre — researchers affiliated with the Université catholique de Louvain in Belgium, which gives the method its name — published "Fast Unfolding of Communities in Large Networks" in…

Donald B.

Michelle Girvan and Mark Newman published "Community Structure in Social and Biological Networks" in 2002, introducing an elegantly simple "divisive" strategy for community detection: rather than trying to build communities up from scratch, progressively…

Otakar Borůvka , a Czech mathematician, published this algorithm in 1926 — three decades before Kruskal's 1956 paper and Prim's 1957 rediscovery (both covered as earlier deep dives in this series).

Reading the fossil record — radiometric dating techniques, index fossils, transitional fossils (Tiktaalik, Archaeopteryx), taphonomy, trace fossils, fossilization processes, biostratigraphy, and integrating paleontological data with molecular evidence.

Boris Weisfeiler and Andrey Leman published this algorithm in 1968 as a practical heuristic for the graph isomorphism problem previewed in Part 18 — decades before Babai's 2015 quasipolynomial breakthrough, and long before anyone could have predicted its…

The Traveling Salesman Problem (TSP) introduced in Part 14 is NP-hard.

In 2019, V.A.

The Lowest Common Ancestor (LCA) problem was first formalized by Aho, Hopcroft, and Ullman in 1973 in the context of string algorithms and data structures.

Heavy-Light Decomposition (HLD) was introduced by Daniel Sleator and Robert Tarjan in 1983 in their landmark paper on dynamic trees and link-cut trees.

Traditional deep learning models like CNNs operate on regular grids (images) and RNNs operate on sequences (text, audio).

In 1980, Harold N.

Yefim Dinitz (also transliterated Dinic), then a young Soviet researcher, published this algorithm in 1970 — as previewed in the Edmonds-Karp deep dive , Dinitz had independently discovered the same BFS-based augmenting-path insight behind Edmonds-Karp's…

In 1969, Robert B.

Yoeng-Jin Chu and Tseng-Hong Liu published this algorithm in 1965, and Jack Edmonds — already met twice in this series, for the Blossom Algorithm and for helping define "polynomial time" itself — independently published an equivalent method in 1967.

Robert Tarjan — already met twice in this series for Tarjan's SCC algorithm and the Chu-Liu/Edmonds refinement from the previous deep dive — introduced the low-link-value DFS technique in the very same landmark 1972 paper, "Depth-First Search and Linear G…

Standard Breadth-First Search (BFS) was introduced by Edward F.

Genomics revolution in evolutionary biology — comparative genomics, gene duplication & genome evolution, horizontal gene transfer, transposable elements, epigenetics & inheritance, CRISPR in evolutionary research, metagenomics, phylogenomics, and future f…

Stephen Warshall published "A Theorem on Boolean Matrices" in the Journal of the ACM in 1962, presenting an elegant $O(V^3)$ algorithm for computing the transitive closure of a binary relation — equivalently, the full reachability matrix of a directed gra…

Before Michael Held and Richard Karp's 1962 dynamic-programming breakthrough (covered in its own deep dive), the earliest computational attacks on TSP were purely combinatorial.

Multi-source BFS is a direct extension of Edward F.

The problem takes its name from Sir William Rowan Hamilton , who in 1857 invented the Icosian Game — a puzzle played on the edges of a dodecahedron, challenging players to find a cycle visiting all 20 vertices exactly once.

Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka published "How Powerful are Graph Neural Networks?"

Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio introduced Graph Attention Networks in their 2018 ICLR paper "Graph Attention Networks."

Topological sorting predates its most famous BFS formulation.

DAG shortest paths are a direct consequence of topological sorting (Tarjan 1972 / Kahn 1962) combined with the relaxation technique formalized by Richard Bellman in his 1958 dynamic-programming treatment of shortest paths.

Greedy coloring is the natural first attempt at any coloring problem, but its weakness — extreme sensitivity to vertex order — motivated better orderings.

Bipartiteness testing traces back to Dénes Kőnig's foundational 1936 graph theory textbook, which formally characterized bipartite graphs as exactly those containing no odd-length cycle — a theorem that translates directly into a linear-time algorithmic t…

Paul Halin introduced treewidth-related ideas in the 1970s, and Neil Robertson and Paul Seymour made tree decompositions foundational to graph-minor theory.

Mikkel Thorup and Uri Zwick's 2005 construction formalized a powerful compromise: exact all-pairs shortest paths are costly to store, but a randomized hierarchy of sampled landmarks can return close answers in constant time.

Miroslav Fiedler's 1973 work connected the second-smallest eigenvalue of the Laplacian to graph connectivity.

Euler's 1752 formula gave the first numerical signature of planar drawings.

Network-flow ideas grew from transportation and logistics.

Gustav Kirchhoff introduced the theorem in 1847 while studying electrical circuits, decades before graph theory had its modern name.

David Karger's 1990s work on randomized min-cut algorithms inspired cut sparsifiers: small weighted subgraphs that approximately preserve every cut.

Union-Find elegantly handles edge insertions, but cannot undo a merge when an edge disappears.

Mirsky and Dilworth transformed questions about partially ordered sets in the mid-twentieth century.

Ford and Fulkerson's 1950s flow framework made capacities algorithmic.