A gentle tutorial on Bock's algorithm for minimum directed spanning trees with a structured reformulation
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, transf...
| Authors | Yuxi Wang, Jungyeul Park |
|---|---|
| Primary category | cs.CL |
| Published | 29 March 2026 |
| Last updated at source | 23 August 2026 |
Silytics shows public metadata from arXiv and links to the original. Information may be incomplete or out of date. Last refreshed 17 October 2026. Licenses and terms of the original apply to the work itself. Not financial, legal or professional advice.