تقرير
To reorient is easier than to orient: an on-line algorithm for reorientation of graphs
| العنوان: | To reorient is easier than to orient: an on-line algorithm for reorientation of graphs |
|---|---|
| المؤلفون: | Fiori-Carones, Marta, Marcone, Alberto |
| المصدر: | Computability, 10 (2021), 215-233 |
| سنة النشر: | 2019 |
| المجموعة: | Computer Science Mathematics |
| مصطلحات موضوعية: | Mathematics - Logic, Computer Science - Logic in Computer Science, Mathematics - Combinatorics |
| الوصف: | 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. Comment: Only minor (non mathematical) changes introduced. To appear in Computability |
| نوع الوثيقة: | Working Paper |
| DOI: | 10.3233/COM-190285 |
| URL الوصول: | http://arxiv.org/abs/1910.01879 |
| رقم الأكسشن: | edsarx.1910.01879 |
| قاعدة البيانات: | arXiv |
| DOI: | 10.3233/COM-190285 |
|---|