{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T10:32:20Z","timestamp":1740133940559,"version":"3.37.3"},"reference-count":5,"publisher":"World Scientific Pub Co Pte Ltd","issue":"02","funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["12071453"],"award-info":[{"award-number":["12071453"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2022,2]]},"abstract":"<jats:p> Given a simple undirected graph [Formula: see text], an orientation of [Formula: see text] is to assign every edge of [Formula: see text] a direction. Borradaile et al gave a greedy algorithm SC-Path-Reversal (in polynomial time) which finds a strongly connected orientation that minimizes the maximum indegree, and conjectured that SC-Path-Reversal is indeed optimal for the \u201dminimizing the lexicographic order\u201d objective as well. In this note, we give a positive answer to the conjecture, which is that we show that the algorithm SC-PATH-REVERSAL finds a strongly connected orientation that minimizes the lexicographic order of indegrees. <\/jats:p>","DOI":"10.1142\/s0129054122500046","type":"journal-article","created":{"date-parts":[[2022,2,24]],"date-time":"2022-02-24T05:20:07Z","timestamp":1645680007000},"page":"149-153","source":"Crossref","is-referenced-by-count":1,"title":["Strongly Connected Orientation with Minimum Lexicographic Order of Indegrees"],"prefix":"10.1142","volume":"33","author":[{"given":"Hongyu","family":"Zhou","sequence":"first","affiliation":[{"name":"School of Mathematical Sciences, University of Science and Technology of China, Hefei, Anhui 230026, P. R. China"}]},{"given":"Xinmin","family":"Hou","sequence":"additional","affiliation":[{"name":"School of Mathematical Sciences, University of Science and Technology of China, Hefei, Anhui 230026, P. R. China"},{"name":"CAS Key Laboratory of Wu Wen-Tsun Mathematics, University of Science and Technology of China, Hefei, Anhui 230026, P. R. China"}]}],"member":"219","published-online":{"date-parts":[[2022,2,23]]},"reference":[{"key":"S0129054122500046BIB001","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054107004644"},{"key":"S0129054122500046BIB002","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00435"},{"journal-title":"Math. Program.","year":"2021","author":"Frank A.","key":"S0129054122500046BIB003"},{"journal-title":"Math. Program.","year":"2021","author":"Frank A.","key":"S0129054122500046BIB004"},{"key":"S0129054122500046BIB006","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2003.07.007"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054122500046","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,3,10]],"date-time":"2022-03-10T04:34:59Z","timestamp":1646886899000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054122500046"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,2]]},"references-count":5,"journal-issue":{"issue":"02","published-print":{"date-parts":[[2022,2]]}},"alternative-id":["10.1142\/S0129054122500046"],"URL":"https:\/\/doi.org\/10.1142\/s0129054122500046","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"type":"print","value":"0129-0541"},{"type":"electronic","value":"1793-6373"}],"subject":[],"published":{"date-parts":[[2022,2]]}}}