Reverse mathematics of some topics from algorithmic graph theory
Volume 157 / 1998
Fundamenta Mathematicae 157 (1998), 1-13
DOI: 10.4064/fm-157-1-1-13
Abstract
This paper analyzes the proof-theoretic strength of an infinite version of several theorems from algorithmic graph theory. In particular, theorems on reachability matrices, shortest path matrices, topological sorting, and minimal spanning trees are considered.
