{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,4]],"date-time":"2026-03-04T07:21:00Z","timestamp":1772608860076,"version":"3.50.1"},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2010,7,29]],"date-time":"2010-07-29T00:00:00Z","timestamp":1280361600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2010,11]]},"DOI":"10.1007\/s00224-010-9280-9","type":"journal-article","created":{"date-parts":[[2010,7,28]],"date-time":"2010-07-28T07:51:24Z","timestamp":1280303484000},"page":"920-933","source":"Crossref","is-referenced-by-count":35,"title":["Local MST Computation with Short Advice"],"prefix":"10.1007","volume":"47","author":[{"given":"Pierre","family":"Fraigniaud","sequence":"first","affiliation":[]},{"given":"Amos","family":"Korman","sequence":"additional","affiliation":[]},{"given":"Emmanuelle","family":"Lebhar","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2010,7,29]]},"reference":[{"key":"9280_CR1","doi-asserted-by":"crossref","unstructured":"Chin, F., Ting, H.F.: An almost linear time and O(nlog\u2009n+e) messages distributed algorithm for minimum-weight spanning trees. In: Proc. 26th IEEE Symp. on Foundations of Computer Science (FOCS), pp.\u00a0257\u2013266 (1985)","DOI":"10.1109\/SFCS.1985.7"},{"key":"9280_CR2","doi-asserted-by":"crossref","unstructured":"Cohen, R., Fraigniaud, P., Ilcinkas, D., Korman, A., Peleg, D.: Labeling schemes for tree representation. In: Proc. 7th International Workshop on Distributed Computing (IWDC), pp.\u00a013\u201324 (2005)","DOI":"10.1007\/11603771_2"},{"key":"9280_CR3","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1007\/11523468_28","volume-title":"32nd Int. Colloquium on Automata, Languages and Programming (ICALP)","author":"R. Cohen","year":"2005","unstructured":"Cohen, R., Fraigniaud, P., Ilcinkas, D., Korman, A., Peleg, D.: Label-guided graph exploration by a finite automaton. In: 32nd Int. Colloquium on Automata, Languages and Programming (ICALP). LNCS, vol. 3580, pp. 335\u2013346. Springer, Berlin (2005)"},{"key":"9280_CR4","volume-title":"Introduction to Algorithms","author":"T.H. Cormen","year":"1990","unstructured":"Cormen, T.H., Leiserson, T., Rivest, R.L.: Introduction to Algorithms. MIT Press\/McGraw-Hill, New York (1990)"},{"key":"9280_CR5","unstructured":"Elkin, M.: A faster distributed protocol for constructing a minimum spanning tree. In: Proc. ACM-SIAM on Discrete Algorithms (SODA), pp.\u00a0352\u2013361 (2004)"},{"key":"9280_CR6","doi-asserted-by":"crossref","unstructured":"Elkin, M.: An unconditional lower bound on the hardness of approximation of distributed minimum spanning tree problem. In: Proc. 36th Annual ACM Symp. on Theory of Computing (STOC), pp.\u00a0331\u2013340 (2004)","DOI":"10.1145\/1007352.1007407"},{"key":"9280_CR7","doi-asserted-by":"crossref","unstructured":"Fraigniaud, P., Ilcinkas, D., Pelc, A.: Oracle size: a new measure of difficulty for communication tasks. In: Proc. 25th Annual ACM Symposium on Principles of Distributed Computing (PODC), pp.\u00a0179\u2013187 (2006)","DOI":"10.1145\/1146381.1146410"},{"key":"9280_CR8","series-title":"LNCS","first-page":"24","volume-title":"31st Int. Symp. on Mathematical Foundations of Computer Science (MFCS)","author":"P. Fraigniaud","year":"2006","unstructured":"Fraigniaud, P., Ilcinkas, D., Pelc, A.: Tree exploration with an oracle. In: 31st Int. Symp. on Mathematical Foundations of Computer Science (MFCS). LNCS, vol. 4162, pp. 24\u201337. Springer, Berlin (2006)"},{"key":"9280_CR9","doi-asserted-by":"crossref","unstructured":"Gafni, E.: Improvements in the time complexity of two message-optimal election algorithms. In: Proc 4th ACM Symp. on Principles of Distributed Computing (PODC), pp.\u00a0175\u2013185 (1985)","DOI":"10.1145\/323596.323612"},{"key":"9280_CR10","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1145\/357195.357200","volume":"5","author":"R.G. Gallager","year":"1983","unstructured":"Gallager, R.G., Humblet, P.A., Spira, P.M.: A distributed algorithm for minimum-weight spanning trees. ACM Trans. Program. Lang. Syst. 5, 66\u201367 (1983)","journal-title":"ACM Trans. Program. Lang. Syst."},{"key":"9280_CR11","doi-asserted-by":"crossref","unstructured":"Korman, A., Kutten, S.: Distributed verification of minimum spanning trees. In: Proc. 25th Annual Symposium on Principles of Distributed Computing (PODC), pp.\u00a026\u201334 (2006)","DOI":"10.1145\/1146381.1146389"},{"key":"9280_CR12","doi-asserted-by":"crossref","unstructured":"Korman, A., Kutten, S., Peleg, D.: Proof labeling schemes. In: Proc. 24th Annual Symposium on Principles of Distributed Computing (PODC), pp.\u00a09\u201318 (2005)","DOI":"10.1145\/1073814.1073817"},{"key":"9280_CR13","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Moscibroda, T., Wattenhofer, R.: What cannot be compute locally! In: Proc. 23th ACM Symp. on Principles of Distributed Computing (PODC), pp.\u00a0300\u2013309 (2004)","DOI":"10.1145\/1011767.1011811"},{"issue":"1","key":"9280_CR14","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1137\/0221015","volume":"21","author":"N. Linial","year":"1992","unstructured":"Linial, N.: Locality in distributed graph algorithms. SIAM J. Comput. 21(1), 193\u2013201 (1992)","journal-title":"SIAM J. Comput."},{"key":"9280_CR15","doi-asserted-by":"crossref","unstructured":"Lotker, Z., Patt-Shamir, B., Peleg, D.: Distributed MST for constant diameter graphs. In: Proc. 20th ACM Symp. on Principles of Distributed Computing (PODC), pp.\u00a063\u201372 (2001)","DOI":"10.1145\/383962.383984"},{"key":"9280_CR16","doi-asserted-by":"crossref","unstructured":"Lotker, Z., Pavlov, E., Patt-Shamir, B., Peleg, D.: MST construction in O(log\u2009 log n) communication rounds. In: SPAA \u201903: Proceedings of the Fifteenth Annual ACM Symposium on Parallel Algorithms and Architectures, pp.\u00a094\u2013100 (2003)","DOI":"10.1145\/777412.777428"},{"key":"9280_CR17","doi-asserted-by":"crossref","unstructured":"Naor, M., Stockmeyer, L.: What can be computed locally? In: 25th ACM Symposium on Theory of Computing (STOC), pp.\u00a0184\u2013193 (1993)","DOI":"10.1145\/167088.167149"},{"key":"9280_CR18","series-title":"SIAM Monographs on Discrete Mathematics","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898719772","volume-title":"Distributed Computing: A Locality-Sensitive Approach","author":"D. Peleg","year":"2000","unstructured":"Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. SIAM Monographs on Discrete Mathematics. SIAM, Philadelphia (2000)"},{"key":"9280_CR19","doi-asserted-by":"crossref","unstructured":"Peleg, D., Rubinovich, R.: A near-tight lower bound on the time complexity of distributed MST construction. In: 40th IEEE Symp. on Foundations of Computer Science (FOCS), pp.\u00a0253\u2013261 (1999)","DOI":"10.1109\/SFFCS.1999.814597"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-010-9280-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-010-9280-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-010-9280-9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,31]],"date-time":"2019-05-31T19:40:01Z","timestamp":1559331601000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-010-9280-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,7,29]]},"references-count":19,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2010,11]]}},"alternative-id":["9280"],"URL":"https:\/\/doi.org\/10.1007\/s00224-010-9280-9","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,7,29]]}}}