Counted primitive — where it appears
Named by 8 essays across 2 fields — each of them below, with the objects they name alongside it.
Counting on a graph
An instrumented array counts comparisons, swaps, reads and writes, and none of those is what a graph algorithm spends its time on. Three new primitives are needed — an adjacency scanned, a vertex first reached, an edge relaxed — and once they exist, breadth-first and depth-first search turn out to be the same algorithm by every count kept on arrays.
The precondition that removes the queue
Dijkstra maintains a priority queue to discover which vertex is safe to finalise next, and on a directed acyclic graph 65% of its counted work goes into that queue. The order it is discovering is already known. Relaxing in topological order makes exactly one relaxation per arc — 1,536 arcs, 1,536 relaxations — with no queue at all, and negative weights are fine.
Two passes or one, and what the second one costs
Kosaraju's algorithm and Tarjan's find the same strongly connected components of the same graph, in the same class, and one of them examines three times as many arcs as the other. The extra pass everybody counts is not where the difference is — building the reversed graph is, and no statement of "two depth-first passes" mentions it.
The precondition on a function the caller writes
Dijkstra expands 1,582 cells to find a path of 98 across a fifty-square grid. The same loop, with the straight-line distance to the goal added to each key, expands 405 and finds the same 98. The estimate has to be a function the caller supplies, and the guarantee holds only while that function never overestimates — a condition on somebody else's code, not on the graph.
The order that has a depth
One hundred cells, filled in three orders, producing one table. Row order takes ninety-one steps and anti-diagonal order takes nineteen. Nineteen is not a property of the order — it is the longest chain of cells in the recurrence itself, no schedule can get under it, and every count taken until now was a total that could not see it.
Two parameters are not enough either
Two graphs on 1,024 vertices with 3,072 edges each — identical in both numbers every bound in this field is written in. Enumerating every pair of neighbours of every vertex costs 18,480 examinations on one and 42,076 on the other. The quantity that separates them is a third parameter, it is computable in linear time, and it appears in no statement of the problem.
A graph is as hard as its largest cycle
Negative arcs rule out Dijkstra's algorithm and leave Bellman–Ford, which on a thousand vertices does three million units of work. Stopping it when a pass changes nothing brings that to 78,496. Finding the strongly connected components first and running it inside each one brings it to 38,549 — and to a quarter of the early-exit cost when the components are small, because every cycle lives inside one.
A bound right for the wrong reason
Orient every edge of a graph towards its higher-degree endpoint and count triangles among out-neighbours, and the work is O(E·d), where d is the graph's degeneracy. The usual reason given is that the orientation keeps every out-degree at most d. On a graph of 1,024 vertices with degeneracy four, 136 vertices have more than four out-neighbours and one has seven. The bound survives by a different argument, and the orientation that does keep every out-degree at most d does less work.
Named alongside it
The objects these essays reach for when they reach for this one.
Measured countDijkstra's algorithmRelaxationShortest pathSparse graphTopological sortTrade offBellman–FordComplexity classCondensationDegeneracyDegree distribution