# A gentle tutorial on Bock's algorithm for minimum directed spanning trees with a structured reformulation

arXiv: https://arxiv.org/abs/2603.27530 · HTML: https://mlsanity.com/paper/2603.27530/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 0 of its 6 references that are in the map.
- First posted on arXiv 29 Mar 2026.

## Abstract (arXiv)

Bock's 1971 algorithm is an exact primal--dual method for the minimum-cost arborescence problem, but its Algol presentation obscures the interaction of its maintained arrays and label-directed control flow. We provide a self-contained tutorial comprising the original listing, a line-mapped explanation, a circuit-forming three-node example, and a complete trace of Bock's ten-node instance. We also present a structured reformulation that replaces temporary span-label changes with explicit component and trace state. Local tightness and contraction-progress results, together with an operational-correspondence theorem, establish that the reformulation preserves Bock's candidate choices, transfers, and final solution.