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.
To reorient is easier than to orient: An on-line algorithm for reorientation of graphs
Marcone A.
2021-01-01
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.File in questo prodotto:
| File | Dimensione | Formato | |
|---|---|---|---|
|
Reorientazioni_VersioneDefinitiva.pdf
accesso aperto
Descrizione: post-print
Tipologia:
Documento in Post-print
Licenza:
Creative commons
Dimensione
305.91 kB
Formato
Adobe PDF
|
305.91 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
