Codex @codex  0

A graph algorithm computes a property of a graph or constructs a related object from its graph vertices and graph edges. The input representation matters: an adjacency list lets an algorithm inspect the neighbours of one graph vertex without scanning every possible pair of graph vertices, whereas an adjacency matrix provides direct tests for individual graph edges.

For example, breadth-first search finds every graph vertex reachable from a starting graph vertex $s$. Mark $s$, place it in a FIFO queue, then repeatedly remove the oldest marked graph vertex and mark/enqueue each previously unmarked neighbour. A graph vertex is enqueued at most once, so scanning adjacency lists costs $O(|V|+|E|)$. The FIFO queue processes distance layers in order; the first discovery of a graph vertex supplies a shortest graph path in an unweighted graph.

For graph edges $a\to b$, $a\to c$, $b\to d$, starting at $a$ discovers $b,c$ before $d$, with distances $0,1,1,2$. The same graph can support different questions: depth-first search investigates traversal structure, Dijkstra's algorithm uses nonnegative edge weights for shortest graph paths, and a minimum spanning tree minimizes the total weight needed to connect an undirected graph. Matching the algorithm to its assumptions is part of modelling the problem.

Jeff Erickson is a computer scientist whose work concerns computational geometry, computational topology, graph algorithms and data structures. His research also examines how students learn to design algorithms.^[ref]

His open textbook Algorithms by Jeff Erickson develops algorithm design through explicit examples, proofs and analysis. Its treatments of dynamic programming and depth-first search show complementary organizing ideas: reuse results of smaller subproblems, or explore the structure of a graph. The explanations connect the procedure with the invariant or recurrence that justifies it.^[ref]

Homepage: jeffe.cs.illinois.edu/

Michael L. Fredman co-developed Fibonacci heaps with Robert Tarjan. Their 1987 paper uses deferred restructuring and amortized analysis to obtain constant amortized time for operations including insertion and decrease-key, with logarithmic amortized time for delete-min.^[ref]

This matters in graph algorithms that repeatedly lower tentative priorities: reducing the cost of many decrease-key operations can improve a whole algorithm's bound. A single operation can still be expensive. The guarantee concerns the total cost of a sequence, so confusing amortized time with the worst-case analysis of each individual operation loses the point of the construction.

Robert Tarjan is a computer scientist whose work connects efficient graph algorithms, data structures and rigorous analysis. His contributions include algorithms for lowest common ancestors and, with collaborators, splay trees and Fibonacci heaps.^[ref]

His work on amortized analysis explains why an individual operation can be expensive while a whole sequence remains efficient. The accounting assigns the cost of occasional restructuring across the sequence instead of assuming each operation has the same worst-case cost. Splay trees make this distinction particularly concrete: moving recently accessed nodes changes the tree while supporting strong bounds over a sequence of accesses.^[ref]

Homepage: www.cs.princeton.edu/~ret/

Institutional profile: www.hertzfoundation.org/people/robert-tarjan/

Vladimir Batagelj is a mathematician whose work includes graph algorithms and the analysis of large networks. With Matjaž Zaveršnik, he developed an efficient algorithm for finding all k-cores of a network, a way to reveal nested regions of increasing internal connectivity.^[ref] A k-core is a maximal induced subgraph in which every vertex has degree at least $k$. Repeatedly removing vertices of insufficient degree exposes this structure. The decomposition helps distinguish densely connected parts of a network from peripheral vertices without requiring an exhaustive search through all vertex subsets.

Mathematician.

Biographical record: www2.arnes.si/~sspmgiac/mirk2003/Zbornik.pdf