To reorient is easier than to orient: An on-line algorithm for reorientation of graphs
Marta Fiori-Carones, Alberto Marcone · Computability · 2021
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 [Formula: see text] and hence is computably true.