{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,3]],"date-time":"2026-02-03T16:49:01Z","timestamp":1770137341512,"version":"3.49.0"},"reference-count":22,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2015,1,13]],"date-time":"2015-01-13T00:00:00Z","timestamp":1421107200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Austrian National Research Network S11403-N23 (RiSE) of the Austrian Science Fund (FWF)"},{"name":"Vienna Science and Technology Fund (WWTF) grant PROSEED"},{"name":"Austrian Science Fund (FWF) projects FATAL (P21694) and SIC (P26436) and the Austrian National Research Network RISE (S11405)"},{"name":"Texas Higher Education Coordinating Board","award":["ARP 000512-0130-2007 and ARP 000512-0007-2006"],"award-info":[{"award-number":["ARP 000512-0130-2007 and ARP 000512-0007-2006"]}]},{"name":"NSF","award":["0500265 and 0964696"],"award-info":[{"award-number":["0500265 and 0964696"]}]},{"name":"FWF projects P20529 and P18264"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2015,1,13]]},"abstract":"<jats:p>Link reversal is a versatile algorithm design paradigm, originally proposed by Gafni and Bertsekas in 1981 for routing and subsequently applied to other problems including mutual exclusion, leader election, and resource allocation. Although these algorithms are well known, until now there have been only preliminary results on time complexity, even for the simplest link reversal algorithm for routing, called Full Reversal. In Full Reversal, a sink reverses all its incident links, whereas in other link reversal algorithms (e.g., Partial Reversal), a sink reverses only some of its incident links. Charron-Bost et al. introduced a generalization, called LR, that includes Full and Partial Reversal as special cases. In this article, we present an exact expression for the time complexity of LR. The expression is stated in terms of simple properties of the initial graph. The result specializes to exact formulas for the time complexity of any node in any initial acyclic directed graph for both Full and Partial Reversal. Having the exact formulas provides insight into the behavior of Full and Partial Reversal on specific graph families. Our first technical insight is to describe the behavior of Full Reversal as a dynamical system and to observe that this system is linear in min-plus algebra. Our second technical insight is to overcome the difficulty posed by the fact that LR is not linear by transforming every execution of LR from an initial graph into an execution of Full Reversal from a different initial graph while maintaining the execution's work and time complexity.<\/jats:p>","DOI":"10.1145\/2644815","type":"journal-article","created":{"date-parts":[[2015,1,16]],"date-time":"2015-01-16T14:29:58Z","timestamp":1421418598000},"page":"1-39","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Time Complexity of Link Reversal Routing"],"prefix":"10.1145","volume":"11","author":[{"given":"Bernadette","family":"Charron-Bost","sequence":"first","affiliation":[{"name":"CNRS \/ LIX, Ecole polytechnique, Palaiseau Cedex, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Matthias","family":"F\u00fcgger","sequence":"additional","affiliation":[{"name":"TU Wien, Wien, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jennifer L.","family":"Welch","sequence":"additional","affiliation":[{"name":"Texas A&amp;M University, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Josef","family":"Widder","sequence":"additional","affiliation":[{"name":"TU Wien, Wien, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2015,1,13]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/1926829.1926864"},{"key":"e_1_2_1_2_1","volume-title":"Geert Jan Olsder, and Jean-Pierre Quadrat","author":"Baccelli Francois","year":"1993","unstructured":"Francois Baccelli , Guy Cohen , Geert Jan Olsder, and Jean-Pierre Quadrat . 1993 . Synchronization and Linearity. John Wiley & Sons . Francois Baccelli, Guy Cohen, Geert Jan Olsder, and Jean-Pierre Quadrat. 1993. Synchronization and Linearity. John Wiley & Sons."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/69558.69560"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/777412.777446"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704443598"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1780.1804"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/2032229.2032243"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/2032229.2032244"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/110843095"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2007.70792"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCOM.1981.1094876"},{"key":"e_1_2_1_12_1","volume-title":"Geert Jan Olsder, and Jacob von der Woude","author":"Heidergott Bernd","year":"2006","unstructured":"Bernd Heidergott , Geert Jan Olsder, and Jacob von der Woude . 2006 . Max Plus at Work. Princeton University Press . Bernd Heidergott, Geert Jan Olsder, and Jacob von der Woude. 2006. Max Plus at Work. Princeton University Press."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-013-0184-1"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the 2000 International Conference on Network Protocols (ICNP'00)","author":"Ko Young-Bae","unstructured":"Young-Bae Ko and N. H. Vaidya . 2000. GeoTORA: A protocol for geocasting in mobile ad hoc networks . In Proceedings of the 2000 International Conference on Network Protocols (ICNP'00) . 240--250. Young-Bae Ko and N. H. Vaidya. 2000. GeoTORA: A protocol for geocasting in mobile ad hoc networks. In Proceedings of the 2000 International Conference on Network Protocols (ICNP'00). 240--250."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01769705"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the 5th International Workshop on Distributed Algorithms (WDAG'91)","author":"Malka Yossi","year":"1991","unstructured":"Yossi Malka and Sergio Rajsbaum . 1991 . Analysis of distributed algorithms based on recurrence relations (preliminary version) . In Proceedings of the 5th International Workshop on Distributed Algorithms (WDAG'91) . 242--253. Yossi Malka and Sergio Rajsbaum. 1991. Analysis of distributed algorithms based on recurrence relations (preliminary version). In Proceedings of the 5th International Workshop on Distributed Algorithms (WDAG'91). 242--253."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/345848.345871"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.1996.0041"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the 16th Conference on Computer Communications (Infocom'97)","author":"Park Vincent D.","unstructured":"Vincent D. Park and M. Scott Corson . 1997. A highly adaptive distributed routing algorithm for mobile wireless networks . In Proceedings of the 16th Conference on Computer Communications (Infocom'97) . 1405--1413. Vincent D. Park and M. Scott Corson. 1997. A highly adaptive distributed routing algorithm for mobile wireless networks. In Proceedings of the 16th Conference on Computer Communications (Infocom'97). 1405--1413."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/58564.59295"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2006.94"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1012363200403"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2644815","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2644815","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T06:13:12Z","timestamp":1750227192000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2644815"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,1,13]]},"references-count":22,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2015,1,13]]}},"alternative-id":["10.1145\/2644815"],"URL":"https:\/\/doi.org\/10.1145\/2644815","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,1,13]]},"assertion":[{"value":"2011-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-01-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}