Algorithms & Data Structures
the bound is a claim, and it is checkable
Concept

Density — where it appears

The ratio of a graph's edges to the most it could have, which every bound in two parameters silently assumes a value for. Every bound in two parameters silently assumes a value for it, and sweeping it at fixed size is a different experiment from sweeping the size at fixed density.

Named by 5 essays across 2 fields — each of them below, with the objects they name alongside it.

10010³10³10⁴10⁵10⁶10⁷Vcounted workBreadth-firstDijkstra, binary heapDijkstra, all V queuedBellman–Ford, all passesV from 64 to 2048, sparse, fixed average degreework = scans + visits + relaxations + queue comparisons

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.

graphs · Graph sparse, fixed average degree10010³10³10⁴10⁵10⁶VworkDijkstra, binary heap — E log EDijkstra, all V queued — V^2dense, fixed density10010⁴10⁵VworkDijkstra, binary heap — V + EDijkstra, all V queued — Ethe class is a property of the sweep as much as of the algorithmwork = scans + visits + relaxations + queue comparisons

Two parameters, one bound, no order

With one size parameter the candidate classes are ordered — n beats n log n beats n², always, and comparing two bounds is reading them. With two, E log V and V² have no order at all, and which one is smaller is a property of the graph. Sweeping V at fixed degree and at fixed density are different experiments, and the same algorithm fits different classes in the two.

graphs · Graph adjacency scansrelaxationsqueue comparisonsvisitsBreadth-first14,336Dijkstra, all V queued2,118,656Dijkstra, binary heap56,973Bellman–Ford, all passes50,309,120Prim64,884Kruskal74,008V = 2048, E = 6,144, sparse, fixed average degreeevery segment counted exactly

The queue decides the class, and the pseudocode does not name it

Dijkstra's algorithm is eleven lines of pseudocode with a priority queue in the middle of them. Which queue is not stated, and it is the difference between 56,973 units of work and 2,118,656 on the same graph. Two of the three queues here also fail to fit the class they are famous for, in a regime each.

graphs · Graph 1,00010,00010³bits of select supportpositions inspected, worst casebinary search, no extra bits: 510L=8L=256L=8L=256one position per L onesdense and sparse6,554 ones in 65,536 positions · sub-blocks of 8worst cases, every k

Select is not rank backwards

Rank counts the ones before a position and select finds the position of the k-th one, and only the first has an obvious structure. The constant-time answer costs 1.56 bits per one, is bounded in a unit the machine does not charge for, and on a vector with one bit in fifty it inspects more positions than the binary search it replaced.

machine · Index 24816326412825510⁶10⁷average out-degreecounted workBellman–Ford from every sourceJohnson's reweightingFloyd–Warshall256 vertices, every answer comparedwork: relaxations + heap comparisons

One Bellman–Ford buys every Dijkstra

A directed graph of 256 vertices with a third of its arcs negative needs shortest paths between every pair. Running Bellman–Ford from every source costs 25.8 million counted operations on the densest graph drawn; running it once, repricing every arc by what it found, and then running Dijkstra from every source costs 13.1 million, and the one Bellman–Ford is under one per cent of that. Floyd–Warshall's 16.8 million is never the cheapest count on the plate. On the sparsest graphs the repeated Bellman–Ford wins, because its early exit makes nine passes rather than 255.

graphs · Graph

Named alongside it

The objects these essays reach for when they reach for this one.

Dijkstra's algorithmAdjacencySparse graphBinary heapHeapSearch frontierTwo parameter boundWorst caseAmortised analysisBellman–FordBit vectorConstant time

All concepts