Reverse mathematics of some topics from algorithmic graph theory

Volume 157 / 1998

Peter G. Clote, Jeffry L. Hirst 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.

Authors

  • Peter G. Clote
  • Jeffry L. Hirst

Search for IMPAN publications

Query phrase too short. Type at least 4 characters.

Rewrite code from the image

Reload image

Reload image