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

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.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11390/1208762
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact