{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,30]],"date-time":"2026-04-30T02:51:44Z","timestamp":1777517504853,"version":"3.51.4"},"reference-count":14,"publisher":"SAGE Publications","issue":"3","license":[{"start":{"date-parts":[[2021,2,2]],"date-time":"2021-02-02T00:00:00Z","timestamp":1612224000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["Computability"],"published-print":{"date-parts":[[2021,7,14]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.3233\/com-190285","type":"journal-article","created":{"date-parts":[[2021,2,2]],"date-time":"2021-02-02T14:21:08Z","timestamp":1612275668000},"page":"215-233","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":1,"title":["To reorient is easier than to orient: An on-line algorithm for reorientation of graphs"],"prefix":"10.1177","volume":"10","author":[{"given":"Marta","family":"Fiori-Carones","sequence":"first","affiliation":[{"name":"Dipartimento di scienze matematiche, informatiche e fisiche, Universit\u00e0 di Udine, Via delle Scienze 208, 33100 Udine, Italy."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alberto","family":"Marcone","sequence":"additional","affiliation":[{"name":"Dipartimento di scienze matematiche, informatiche e fisiche, Universit\u00e0 di Udine, Via delle Scienze 208, 33100 Udine, Italy."}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","published-online":{"date-parts":[[2021,2,2]]},"reference":[{"key":"ref001","doi-asserted-by":"publisher","DOI":"10.1017\/bsl.2019.20"},{"key":"ref002","unstructured":"C.\u00a0Berge, Graphs and Hypergraphs, 2nd edn, North-Holland, Amsterdam, 1976."},{"key":"ref003","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-59234-9"},{"key":"ref004","unstructured":"T.H.\u00a0Cormen, C.E.\u00a0Leiserson, R.L.\u00a0Rivest and C.\u00a0Stein, Introduction to Algorithms, 3rd edn, MIT Press, Massachusetts, 2009."},{"key":"ref005","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(85)90042-1"},{"key":"ref006","doi-asserted-by":"publisher","DOI":"10.1007\/BF02020961"},{"key":"ref007","first-page":"1370","volume":"254","author":"Ghouila-Houri A.","year":"1962","journal-title":"Les Comptes Rendus de l\u2019Acad\u00e9mie des Sciences"},{"key":"ref008","doi-asserted-by":"publisher","DOI":"10.24033\/asens.1132"},{"key":"ref009","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1964-055-5"},{"key":"ref010","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-5060(04)80051-7"},{"key":"ref011","unstructured":"E.\u00a0Harzheim, Ordered Sets, Springer, New York, 2005."},{"key":"ref012","unstructured":"J.L.\u00a0Hirst, Combinatorics in subsystems of second order arithmetic, PhD thesis, The Pennsylvania State University, 1987."},{"key":"ref013","unstructured":"F.\u00a0Maffray and M.\u00a0Preissmann, A translation of T. Gallai\u2019s paper: \u201cTransitiv orientierbare Graphen\u201d, in: Perfect Graphs, J.L.\u00a0Ram\u00edrez-Alfons\u00edn and B.A.\u00a0Reed, eds, Wiley, New York, 2001, pp.\u00a025\u201366."},{"key":"ref014","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511581007"}],"container-title":["Computability"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/COM-190285","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.3233\/COM-190285","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/COM-190285","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,28]],"date-time":"2026-04-28T16:02:49Z","timestamp":1777392169000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/full\/10.3233\/COM-190285"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,2,2]]},"references-count":14,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,7,14]]}},"alternative-id":["10.3233\/COM-190285"],"URL":"https:\/\/doi.org\/10.3233\/com-190285","relation":{},"ISSN":["2211-3568","2211-3576"],"issn-type":[{"value":"2211-3568","type":"print"},{"value":"2211-3576","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,2,2]]}}}