{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:18:33Z","timestamp":1759637913378},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2012,7,20]],"date-time":"2012-07-20T00:00:00Z","timestamp":1342742400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2014,2]]},"DOI":"10.1007\/s00453-012-9674-y","type":"journal-article","created":{"date-parts":[[2012,7,19]],"date-time":"2012-07-19T20:38:52Z","timestamp":1342730332000},"page":"337-357","source":"Crossref","is-referenced-by-count":9,"title":["Finding Best Swap Edges Minimizing the Routing Cost of a Spanning Tree"],"prefix":"10.1007","volume":"68","author":[{"given":"Davide","family":"Bil\u00f2","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Luciano","family":"Gual\u00e0","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guido","family":"Proietti","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2012,7,20]]},"reference":[{"key":"9674_CR1","doi-asserted-by":"crossref","first-page":"118","DOI":"10.1007\/BF01459088","volume":"99","author":"W. Ackermann","year":"1928","unstructured":"Ackermann, W.: Zum hilbertschen Aufbau der reellen Zahlen. Math. Ann. 99, 118\u2013133 (1928)","journal-title":"Math. Ann."},{"key":"9674_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"508","DOI":"10.1007\/3-540-45995-2_44","volume-title":"Theoretical Informatics, 5th Latin American Symposium (LATIN)","author":"M.A. Bender","year":"2002","unstructured":"Bender, M.A., Farach-Colton, M.: The level ancestor problem simplified. In: Rajsbaum, S. (ed.) Theoretical Informatics, 5th Latin American Symposium (LATIN). Lecture Notes in Computer Science, vol.\u00a02286, pp.\u00a0508\u2013515. Springer, Berlin (2002)"},{"issue":"4","key":"9674_CR3","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1007\/BF01187017","volume":"11","author":"H. Booth","year":"1994","unstructured":"Booth, H., Westbrook, J.: A\u00a0linear algorithm for analysis of minimum spanning and shortest-path trees of planar graphs. Algorithmica 11(4), 341\u2013352 (1994)","journal-title":"Algorithmica"},{"key":"9674_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"716","DOI":"10.1007\/978-3-540-92182-0_63","volume-title":"19th Int. Symposium on Algorithms and Computation (ISAAC)","author":"S. Das","year":"2008","unstructured":"Das, S., Gfeller, B., Widmayer, P.: Computing best swaps in optimal tree spanners. In: Hong, S.-H., Nagamochi, H., Fukunaga, T. (eds.) 19th Int. Symposium on Algorithms and Computation (ISAAC). Lecture Notes in Computer Science, vol.\u00a05369, pp.\u00a0716\u2013727. Springer, Berlin (2008)"},{"issue":"1","key":"9674_CR5","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1016\/j.tcs.2007.03.046","volume":"383","author":"A. Di Salvo","year":"2007","unstructured":"Di Salvo, A., Proietti, G.: Swapping a failing edge of a shortest paths tree by minimizing the average stretch factor. Theor. Comput. Sci. 383(1), 23\u201333 (2007)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"9674_CR6","doi-asserted-by":"crossref","first-page":"700","DOI":"10.1093\/ietisy\/e89-d.2.700","volume":"89-D","author":"P. Flocchini","year":"2006","unstructured":"Flocchini, P., Enriques, A.M., Pagli, L., Prencipe, G., Santoro, N.: Point-of-failure shortest-path rerouting: computing the optimal swap edges distributively. IEICE Trans. 89-D(2), 700\u2013708 (2006)","journal-title":"IEICE Trans."},{"key":"9674_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"268","DOI":"10.1007\/978-3-540-75142-7_22","volume-title":"21st Int. Symposium on Distributed Computing (DISC)","author":"B. Gfeller","year":"2007","unstructured":"Gfeller, B., Santoro, N., Widmayer, P.: A\u00a0distributed algorithm for finding all best swap edges of a minimum diameter spanning tree. In: Pelc, A. (ed.) 21st Int. Symposium on Distributed Computing (DISC). Lecture Notes in Computer Science, vol.\u00a04731, pp.\u00a0268\u2013282. Springer, Berlin (2007)"},{"key":"9674_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"454","DOI":"10.1007\/978-3-540-87744-8_38","volume-title":"16th Annual European Symposium on Algorithms (ESA)","author":"B. Gfeller","year":"2008","unstructured":"Gfeller, B.: Faster swap edge computation in minimum diameter spanning trees. In: Halperin, D., Mehlhorn, K. (eds.) 16th Annual European Symposium on Algorithms (ESA). Lecture Notes in Computer Science, vol.\u00a05193, pp.\u00a0454\u2013465. Springer, Berlin (2008)"},{"issue":"2","key":"9674_CR9","doi-asserted-by":"crossref","first-page":"338","DOI":"10.1137\/0213024","volume":"13","author":"D. Harel","year":"1984","unstructured":"Harel, D., Tarjan, R.E.: Fast algorithms for finding nearest common ancestors. SIAM J. Comput. 13(2), 338\u2013355 (1984)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"9674_CR10","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1016\/0020-0190(89)90136-1","volume":"33","author":"J. Hershberger","year":"1989","unstructured":"Hershberger, J.: Finding the upper envelope of n line segments in O(nlogn) time. Inf. Process. Lett. 33(4), 169\u2013174 (1989)","journal-title":"Inf. Process. Lett."},{"issue":"4","key":"9674_CR11","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1002\/net.3230080402","volume":"8","author":"D. Johnson","year":"1978","unstructured":"Johnson, D., Lenstra, J., Kan, A.R.: The complexity of the network design problem. Networks 8(4), 279\u2013285 (1978)","journal-title":"Networks"},{"issue":"5","key":"9674_CR12","doi-asserted-by":"crossref","first-page":"39","DOI":"10.7155\/jgaa.00039","volume":"5","author":"E. Nardelli","year":"2001","unstructured":"Nardelli, E., Proietti, G., Widmayer, P.: Finding all the best swaps of a minimum diameter spanning tree under transient edge failures. J.\u00a0Graph Algorithms Appl. 5(5), 39\u201357 (2001)","journal-title":"J.\u00a0Graph Algorithms Appl."},{"issue":"1","key":"9674_CR13","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1007\/s00453-002-0988-z","volume":"35","author":"E. Nardelli","year":"2003","unstructured":"Nardelli, E., Proietti, G., Widmayer, P.: Swapping a failing edge of a single source shortest paths tree is good and fast. Algorithmica 35(1), 56\u201374 (2003)","journal-title":"Algorithmica"},{"issue":"3","key":"9674_CR14","first-page":"1","volume":"57","author":"G. Nivasch","year":"2010","unstructured":"Nivasch, G.: Improved bounds and new techniques for Davenport\u2013Schinzel sequences and their generalizations. J.\u00a0ACM 57(3), 1\u201344 (2010)","journal-title":"J.\u00a0ACM"},{"key":"9674_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1007\/978-3-642-10877-8_29","volume-title":"Principles of Distributed Systems, 13th International Conference (OPODIS)","author":"L. Pagli","year":"2009","unstructured":"Pagli, L., Prencipe, G.: Brief announcement: distributed swap edges computation for minimum routing cost spanning trees. In: Abdelzaher, T.F., Raynal, M., Santoro, N. (eds.) Principles of Distributed Systems, 13th International Conference (OPODIS). Lecture Notes in Computer Science, vol.\u00a05923, pp.\u00a0365\u2013371. Springer, Berlin (2009)"},{"key":"9674_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"964","DOI":"10.1007\/11602613_96","volume-title":"16th Int. Symposium on Algorithms and Computation (ISAAC)","author":"S. Pettie","year":"2005","unstructured":"Pettie, S.: Sensitivity analysis of minimum spanning trees in sub-inverse-Ackermann time. In: Deng, X., Du, D.-Z. (eds.) 16th Int. Symposium on Algorithms and Computation (ISAAC). Lecture Notes in Computer Science, vol.\u00a03827, pp.\u00a0964\u2013973. Springer, Berlin (2005)"},{"issue":"1","key":"9674_CR17","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1016\/0020-0190(82)90137-5","volume":"14","author":"R.E. Tarjan","year":"1982","unstructured":"Tarjan, R.E.: Sensitivity analysis of minimum spanning trees and shortest path trees. Inf. Process. Lett. 14(1), 30\u201333 (1982)","journal-title":"Inf. Process. Lett."},{"key":"9674_CR18","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1137\/0601008","volume":"1","author":"R. Wong","year":"1980","unstructured":"Wong, R.: Worst-case analysis of network design problem heuristics. SIAM J. Algebr. Discrete Methods 1, 51\u201363 (1980)","journal-title":"SIAM J. Algebr. Discrete Methods"},{"issue":"3","key":"9674_CR19","doi-asserted-by":"crossref","first-page":"761","DOI":"10.1137\/S009753979732253X","volume":"29","author":"B.Y. Wu","year":"1999","unstructured":"Wu, B.Y., Lancia, G., Bafna, V., Chao, K.-M., Ravi, R., Tang, C.Y.: A\u00a0polynomial-time approximation scheme for minimum routing cost spanning trees. SIAM J. Comput. 29(3), 761\u2013778 (1999)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"9674_CR20","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1016\/S0166-218X(99)00212-7","volume":"102","author":"B.Y. Wu","year":"2000","unstructured":"Wu, B.Y., Chao, K.-M., Tang, C.Y.: Approximation algorithms for some optimum communication spanning tree problems. Discrete Appl. Math. 102(3), 245\u2013266 (2000)","journal-title":"Discrete Appl. Math."},{"issue":"3","key":"9674_CR21","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1007\/s00453-007-9080-z","volume":"50","author":"B.Y. Wu","year":"2008","unstructured":"Wu, B.Y., Hsiao, C.-Y., Chao, K.-M.: The swap edges of a multiple-sources routing tree. Algorithmica 50(3), 299\u2013311 (2008)","journal-title":"Algorithmica"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9674-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-012-9674-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9674-y","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T09:45:10Z","timestamp":1559123110000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-012-9674-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,7,20]]},"references-count":21,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2014,2]]}},"alternative-id":["9674"],"URL":"https:\/\/doi.org\/10.1007\/s00453-012-9674-y","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,7,20]]}}}