{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,17]],"date-time":"2026-07-17T23:07:57Z","timestamp":1784329677914,"version":"3.55.0"},"reference-count":6,"publisher":"Wiley","issue":"4","license":[{"start":{"date-parts":[[2006,10,11]],"date-time":"2006-10-11T00:00:00Z","timestamp":1160524800000},"content-version":"vor","delay-in-days":7619,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[1985,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We study the problem of orienting all the undirected edges of a mixed multigraph so as to preserve reachability. Extending work by Robbins and by Boesch and Tindell, we develop a linear\u2010time algorithm to test whether there is an orientation that preserves strong connectivity and to construct such an orientation whenever possible. This algorithm makes no attempt to minimize distances in the resulting directed graph, and indeed the maximum distance, for example, can blow up by a factor proportional to the number of vertices in the graph. Extending work by Chv\u00e1tal and Thomassen, we then prove that, if a mixed multigraph of radius <jats:italic>r<\/jats:italic> has any strongly connected orientation, it must have an orientation of radius at most 4<jats:italic><jats:sup>2<\/jats:sup><\/jats:italic> + A<jats:italic>r<\/jats:italic>. The proof gives a polynomial\u2010time algorithm for constructing such an orientation.<\/jats:p>","DOI":"10.1002\/net.3230150409","type":"journal-article","created":{"date-parts":[[2007,5,11]],"date-time":"2007-05-11T20:17:36Z","timestamp":1178914656000},"page":"477-484","source":"Crossref","is-referenced-by-count":54,"title":["Strongly connected orientations of mixed multigraphs"],"prefix":"10.1002","volume":"15","author":[{"given":"Fan R. K.","family":"Chung","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michael R.","family":"Garey","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Robert E.","family":"Tarjan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"311","published-online":{"date-parts":[[2006,10,11]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.2307\/2321858"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(78)90078-3"},{"key":"e_1_2_1_4_2","unstructured":"E. L.Johnson andP.Pieroni A linear programming approach to the optimum network orientation problem. Presented at NETFLOW 83: International Workshop on Network Flow Optimization Theory and Practice Pisa Italy 1983."},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.2307\/2303897"},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1137\/0201010"},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1137\/0203006"}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.3230150409","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.3230150409","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,20]],"date-time":"2023-10-20T20:06:51Z","timestamp":1697832411000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.3230150409"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1985,12]]},"references-count":6,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1985,12]]}},"alternative-id":["10.1002\/net.3230150409"],"URL":"https:\/\/doi.org\/10.1002\/net.3230150409","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[1985,12]]}}}