To reorient is easier than to orient: an on-line algorithm for reorientation of graphs

Abstract

We define an on-line (incremental) algorithm that, given a (possibly infinite) pseudo-transitive oriented graph, produces a transitive reorientation. This implies that a theorem of Ghouila-Houri is provable in RCA_0 and hence is computably true.

arXiv commentOnly minor (non mathematical) changes introduced. To appear in Computability

Cited by in corpus (1)

• Primitive recursive reverse mathematics