Two parameters
Counting on a graph
The counted graph this site's second field is built on, why an array's primitives do not generalise, and the first result it produces — that BFS and DFS differ in no measurement of time at all.
Two parameters, one bound, no order
Why a graph bound is not a comparison until the density regime is stated, what a fit in two variables has to do differently, and the measured case where a published class stops describing the algorithm.
The queue decides the class, and the pseudocode does not name it
Three priority queues inside one algorithm, counted separately from the traversal, and the two implementation decisions that decide a complexity class without appearing in any published statement of it.
The constant that is practically constant
The four combinations of union by rank and path compression, measured; what α(n) actually is when it is tabulated rather than quoted; and the one case on this site where the formal class overstates rather than understates.
The precondition that removes the queue
Shortest paths on an acyclic graph, where the topological order is the priority order, the queue has nothing to decide, and the precondition buys something instead of costing it.
Two passes or one, and what the second one costs
Two component algorithms measured against each other — the arcs each examines, the stack one of them holds, and the ordering both of them hand back in opposite directions.
The precondition on a function the caller writes
A* measured against Dijkstra on the same grids, the dial between an admissible estimate and a fast one, and what a precondition looks like when it is about a function rather than about an input.
A list and a block of memory
Adjacency lists against compressed sparse row, with identical counted work and modelled miss counts a factor of 3.6 apart — the two-counts theme at the widest separation it reaches here, and where it fails to.
Two parameters are not enough either
Triangle counting on two graphs a two-parameter bound cannot tell apart, the sum of squared degrees that decides the naive method, and the degeneracy that bounds the oriented one.
The bound with a precondition
Two shortest-path algorithms whose published bounds describe versions nobody runs, the four-vertex graph on which the faster one is simply wrong, and what an algorithm's generality costs when it is measured rather than assumed.
A graph is as hard as its largest cycle
Shortest paths with negative arcs, taken one strongly connected component at a time. Bellman–Ford pays for the whole graph's cycles; the component method pays only for the largest component's, and on a randomly numbered graph it beats the early-exit Bellman–Ford by up to five times while returning identical distances.
An estimate borrowed from an easier problem
A* with the straight-line estimate against A* with landmark distances, on unit grids and on weighted terrain. The straight line is the exact answer to a problem with no terrain in it, and a landmark table is the exact answer to one that has the terrain, which is why one collapses on weighted ground and the other does not.
An estimate is a reweighting
A* with a consistent estimate is Dijkstra on reduced arc costs, checked expansion for expansion. An estimate that is admissible but inconsistent makes some reduced costs negative, breaks Dijkstra's precondition, and returns a longer path unless finished vertices may be reopened — which costs more expansions than the consistent estimate needed.
Where two searches should stop
Bidirectional Dijkstra with two stopping rules, measured over many grids. Stopping where the searches meet returns a longer path on weighted terrain one time in eight; stopping when the frontiers' smallest keys together reach the best route across any arc is always right, and expands 64 to 75 per cent of what a one-ended search does rather than the half the geometry promises.
A bound right for the wrong reason
The degree orientation used for triangle counting, measured against the degeneracy it is said to be bounded by. Its out-degrees exceed the degeneracy on every graph drawn, so the usual argument for its O(E·d) bound is false; the bound holds through the sum over edges of the smaller endpoint degree. An orientation taken from the degeneracy computation itself keeps every out-degree at or below d and examines 5% to 25% fewer pairs.
Two estimates that must agree
Two-ended A* on weighted and unit-cost grids, combined three ways. Separate estimates with the sum stopping rule stop too early on 12 of 40 weighted grids; a rule that waits for either frontier alone is correct and expands three times as much; an averaged potential is correct on every grid and costs 4% more than the incorrect search — while on unit-cost grids none of the combinations improves on A* from one end.
One Bellman–Ford buys every Dijkstra
All-pairs shortest paths on directed graphs with negative arcs and no negative cycle, by Bellman–Ford from every source, by Johnson's reweighting and by Floyd–Warshall, counted against density at 256 and 512 vertices. Johnson's reweighting is the same construction as A*'s potential with the potential computed rather than supplied; its preparation is under 1% of its work, it wins from an average out-degree of eight, and repeated Bellman–Ford wins below that.
Where the landmarks stand
The landmark estimate for A* on weighted grids, with its landmark cells placed at the corners, near the centre, at random and by farthest-point selection, and with one to eight of them. Placement changes the cells expanded per query by a factor of 3.4 at a fixed number of landmarks; the corners beat farthest-point selection on every map, because farthest-point selection's fourth landmark lands in the interior.
What the queries know that the map does not
Greedy landmark selection from a sample of observed queries, measured against corner placement on eight weighted maps, under uniform queries and under queries drawn to one, two, four and eight destinations — with the preparation priced in the same unit it saves.
A stop that is correct and never sooner
The combined stopping rule for bidirectional A* under a shared potential, measured against the sum rule alone on forty weighted grids — with the two frontiers' own keys traced expansion by expansion, the bookkeeping priced in work and in queue entries, and the alternation swept to find where the second rule could fire at all.
How long a reweighting stays true
Single-source shortest-path queries on graphs with negative arcs, priced as Bellman–Ford per query against one stored reweighting and Dijkstra — with the break-even query count swept against density, and the stored potential's survival measured against the share of arcs whose costs change between queries.
A potential mended where it broke
Johnson's stored potential under updates, repaired by a queue-driven relaxation from the broken arcs instead of recomputed from the virtual source: the total work against Bellman–Ford per query as arcs are redrawn, the relaxations a repair makes, how many vertices it changes, and the same three measurements when whole vertices' hidden potentials move.
A placement after the traffic moved
Landmarks chosen from a query log that points at one destination, measured after the destination moves: the decay of their advantage with distance, the price of choosing again against what a good choice saves, and four policies — the corners, one fit kept, a refit on a schedule, a refit on a counter — on drifting streams with every selection charged.
A refit that changes one landmark
Landmark refits on weighted terrain maps, every selection charged: what keeping three landmarks and re-choosing one costs against a full selection, five policies on streams whose destination drifts and on streams whose destination jumps at random times, where each policy's cells go, and one jumping stream drawn query by query.
The candidates near where the queries end
Landmark refits on weighted 50 × 50 mazes that keep three landmarks and re-choose the fourth, with the replacement tried only on the k candidates nearest the sample's destination: the price against a full selection and the quality on fresh queries for k from 2 to all 24, where the unrestricted refit's winner ranks by distance, one refit drawn on its map, and a counter firing the restricted refit on streams whose destination jumps, at four window lengths.
Starting from the corners
Landmark placements on weighted 50 × 50 mazes, four landmarks, every search charged in cells expanded, on streams of 30,000 queries whose destination jumps or drifts: a counter that starts at the corners and uses only refits restricted to four candidates, and one that keeps three corners for good, against the corners, one full selection, and the counter that starts with a full selection — cost against the jump rate, cost against the counter's window, the preparation each start spends, one stream traced, and drifting streams.
A refit priced before it is made
Landmark placements on weighted mazes of 2,500 cells, four maps and 30,000 queries a stream, whose destination jumps on average every 1,000 to 10,000 queries or drifts a step with chance 0.001 to 0.03 before each query, every search charged: the corners; one full selection kept; a counter that starts with a full selection; the corner start with its counter; and the corner start that every window prices its placement against four nearby candidates on the last twenty queries and refits when the estimated saving exceeds the last refit's price — cells a query on jumps and drifts, what watching costs by window, one drifting stream, and how often each refits.
A horizon the stream can supply
Landmark placements on weighted mazes of 2,500 cells, four maps and 30,000 queries a stream, whose destination jumps every 1,000 to 10,000 queries or drifts a step with chance 0.001 to 0.03: the watching corner start with its estimated saving scaled to the window, to the mean interval between its own refits, to the mean spell of one destination, to the mean stretch of traffic within ten cells of one destination, and to the true future. The intervals between refits, cells a query on jumps and drifts, where the cost goes at one jump in 1,000, and traffic that changes pace halfway.
A watch that looks less
Landmark placements on four weighted mazes of 2,500 cells, 30,000 queries a stream, the destination jumping every 1,000 to 10,000 queries, drifting a step with chance 0.001 to 0.03, or changing pace halfway: the corners, the watch scaled to its window, the watch with a horizon learned from traffic within ten cells of one destination, and two watches that change how often they look — doubling and halving between 1,000 and 8,000 queries, and two states, 1,000 or 8,000. Where the cells go at one jump in 1,000, cells a query by jump rate and by drift, one stream's intervals, the share of each stream at each interval, and the streams that change pace.