{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,19]],"date-time":"2025-03-19T11:58:08Z","timestamp":1742385488175},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540405344"},{"type":"electronic","value":"9783540450719"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/3-540-45071-8_41","type":"book-chapter","created":{"date-parts":[[2007,10,27]],"date-time":"2007-10-27T08:04:43Z","timestamp":1193472283000},"page":"404-414","source":"Crossref","is-referenced-by-count":2,"title":["Optimal MST Maintenance for Transient Deletion of Every Node in Planar Graphs"],"prefix":"10.1007","author":[{"given":"Carlo","family":"Gaibisso","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guido","family":"Proietti","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Richard B.","family":"Tan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2003,6,24]]},"reference":[{"key":"41_CR1","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1007\/BF01187017","volume":"11","author":"H. Booth","year":"1994","unstructured":"H. Booth and J. Westbrook, A linear algorithm for analysis of minimum spanning and shortest-path trees of planar graphs, Algorithmica 11 (1994) 341\u2013352.","journal-title":"Algorithmica"},{"key":"41_CR2","doi-asserted-by":"crossref","unstructured":"A.L. Buchsbaum, H. Kaplan, A. Rogers and J. Westbrook, Linear-time pointermachine algorithms for least common ancestors, MST verification, and dominators, Proc. of the 30th Annual ACM Symposium on Theory of Computing (STOC\u201998), (1998) 279\u2013288.","DOI":"10.1145\/276698.276764"},{"issue":"4","key":"41_CR3","doi-asserted-by":"publisher","first-page":"724","DOI":"10.1137\/0205051","volume":"5","author":"D. Cheriton","year":"1976","unstructured":"D. Cheriton and R.E. Tarjan, Finding minimum spanning trees, SIAM J. Comput., 5(4) (1976) 724\u2013742.","journal-title":"SIAM J. Comput."},{"issue":"3","key":"41_CR4","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1016\/0022-0000(78)90022-3","volume":"16","author":"F. Chin","year":"1978","unstructured":"F. Chin and D. Houck, Algorithms for updating minimal spanning trees, J. Comput. System Sci., 16(3) (1978) 333\u2013344.","journal-title":"J. Comput. System Sci."},{"issue":"2","key":"41_CR5","doi-asserted-by":"publisher","first-page":"471","DOI":"10.1137\/S0097539795285916","volume":"28","author":"F.Y.L. Chin","year":"1998","unstructured":"F.Y.L. Chin, C.A. Wang, Finding the constrained Delaunay triangulation and constrained Voronoi diagram of a simple polygon in linear time, SIAM J. Comput., 28(2) (1998) 471\u2013486.","journal-title":"SIAM J. Comput."},{"key":"41_CR6","series-title":"Lect Notes Comput Sci","first-page":"197","volume-title":"Proc. of the Third Workshop on Randomization, Approximation and Combinatorial Optimization (RANDOMAPPROX\u2019 99)","author":"A.E.F. Clementi","year":"2004","unstructured":"A.E.F. Clementi, P. Penna and R. Silvestri, Hardness results for the power range assignment problem in packet radio networks, Proc. of the Third Workshop on Randomization, Approximation and Combinatorial Optimization (RANDOMAPPROX\u2019 99), Vol. 1671 of Lecture Notes in Computer Science, Springer, 197\u2013208."},{"key":"41_CR7","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1007\/3-540-44693-1_11","volume-title":"Proc. of the 18th Annual Symposium on Theoretical Aspects of Computer Science (STACS\u201901)","author":"A.E.F. Clementi","year":"2001","unstructured":"A.E.F. Clementi, P. Crescenzi, P. Penna, G. Rossi and P. Vocca, On the complexity of computing minimum energy consumption broadcast subgraphs, Proc. of the 18th Annual Symposium on Theoretical Aspects of Computer Science (STACS\u201901), Vol. 2010 of Lecture Notes in Computer Science, Springer, 121\u2013131."},{"key":"41_CR8","doi-asserted-by":"publisher","first-page":"530","DOI":"10.1007\/s00453-001-0061-3","volume":"31","author":"B. Das","year":"2001","unstructured":"B. Das and M.C. Loui, Reconstructing a minimum spanning tree after deletion of any node, Algorithmica 31 (2001) 530\u2013547. Also available as TR UILU-ENG-95-2241 (ACT-136), University of Illinois at Urbana-Champaign, IL, 1995.","journal-title":"Algorithmica"},{"issue":"6","key":"41_CR9","doi-asserted-by":"publisher","first-page":"1184","DOI":"10.1137\/0221070","volume":"21","author":"B. Dixon","year":"1992","unstructured":"B. Dixon, M. Rauch and R.E. Tarjan, Verification and sensitivity analysis of minimum spanning trees in linear time, SIAM J. Comput., 21(6) (1992) 1184\u20131192.","journal-title":"SIAM J. Comput."},{"issue":"2","key":"41_CR10","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1006\/jagm.1994.1033","volume":"17","author":"D. Eppstein","year":"1994","unstructured":"D. Eppstein, Offline algorithms for dynamic minimum spanning tree problems, J. of Algorithms, 17(2) (1994) 237\u2013250.","journal-title":"J. of Algorithms"},{"key":"41_CR11","doi-asserted-by":"crossref","unstructured":"C. Gaibisso, G. Proietti and R. Tan, Efficient management of transient station failures in linear radio communication networks with bases, 2nd International Workshop on Approximation and Randomized Algorithms in Communication Networks (ARACNE\u201901). Vol. 12 of Proceedings in Informatics, Carleton Scientific, 37\u201354.","DOI":"10.1016\/j.jpdc.2005.11.002"},{"key":"41_CR12","doi-asserted-by":"crossref","DOI":"10.21236\/AD0705364","volume-title":"Graph theory","author":"F. Harary","year":"1969","unstructured":"F. Harary, Graph theory, Addison-Wesley, Reading, MA, 1969."},{"key":"41_CR13","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1007\/BFb0023473","volume-title":"Proc. of the 14th Annual Symposium on Theoretical Aspects of Computer Science (STACS\u201997)","author":"L.M. Kirousis","year":"1997","unstructured":"L.M. Kirousis, E. Kranakis, D. Krizanc and A. Pelc, Power consumption in packet radio networks, Proc. of the 14th Annual Symposium on Theoretical Aspects of Computer Science (STACS\u201997), Vol. 1200 of Lecture Notes in Computer Science, Springer, 363\u2013374."},{"key":"41_CR14","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1007\/3-540-68530-8_24","volume-title":"6th European Symposium on Algorithms (ESA\u201998)","author":"E. Kranakis","year":"1998","unstructured":"E. Kranakis, D. Krizanc and A. Pelc, Fault-tolerant broadcasting in radio networks, 6th European Symposium on Algorithms (ESA\u201998), Vol. 1461 of Lecture Notes in Computer Science, Springer-Verlag, 283\u2013294."},{"key":"41_CR15","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"346","DOI":"10.1007\/3-540-45253-2_32","volume-title":"8th European Symposium on Algorithms (ESA 2000)","author":"E. Nardelli","year":"2000","unstructured":"E. Nardelli, G. Proietti and P. Widmayer, Maintaining a minimum spanning tree under transient node failures, 8th European Symposium on Algorithms (ESA 2000), Vol. 1879 of Lecture Notes in Computer Science, Springer, 346\u2013355."},{"key":"41_CR16","doi-asserted-by":"crossref","unstructured":"E. Pagani and G.P. Rossi, Reliable broadcast in mobile multihop packet networks, Third Annual ACM\/IEEE Int. Conf. on Mobile Computing and Networking (MOBICOM\u201997), 34\u201342.","DOI":"10.1145\/262116.262125"},{"key":"41_CR17","volume-title":"Wireless Information Networks","author":"K. Pahvalan","year":"1995","unstructured":"K. Pahvalan and A. Levesque, Wireless Information Networks, Wiley-Interscience, New York, 1995."},{"issue":"2","key":"41_CR18","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1145\/321879.321884","volume":"22","author":"R.E. Tarjan","year":"1975","unstructured":"R.E. Tarjan, Efficiency of a good but not linear set union algorithm, J. of the ACM, 22(2) (1975) 215\u2013225.","journal-title":"J. of the ACM"},{"issue":"4","key":"41_CR19","doi-asserted-by":"publisher","first-page":"690","DOI":"10.1145\/322154.322161","volume":"26","author":"R.E. Tarjan","year":"1979","unstructured":"R.E. Tarjan, Applications of path compression on balanced trees, J. of the ACM, 26(4) (1979) 690\u2013715.","journal-title":"J. of the ACM"},{"key":"41_CR20","doi-asserted-by":"crossref","unstructured":"P.J. Wan, G. Calinescu, X.Y. Li and O. Frieder, Minimum-energy broadcast routing in static ad hoc wireless networks, Proc. of the 20th Annual Conference on Computer Communications (INFOCOM\u201901), 1162\u20131171.","DOI":"10.1109\/INFCOM.2001.916310"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45071-8_41","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,4]],"date-time":"2019-05-04T02:09:12Z","timestamp":1556935752000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45071-8_41"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540405344","9783540450719"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/3-540-45071-8_41","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2003]]}}}