{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T01:53:19Z","timestamp":1725846799873},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662491911"},{"type":"electronic","value":"9783662491928"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-662-49192-8_16","type":"book-chapter","created":{"date-parts":[[2016,1,7]],"date-time":"2016-01-07T15:47:27Z","timestamp":1452181647000},"page":"195-207","source":"Crossref","is-referenced-by-count":1,"title":["Online Minimum Spanning Tree with Advice"],"prefix":"10.1007","author":[{"given":"Maria Paola","family":"Bianchi","sequence":"first","affiliation":[]},{"given":"Hans-Joachim","family":"B\u00f6ckenhauer","sequence":"additional","affiliation":[]},{"given":"Tatjana","family":"Br\u00fclisauer","sequence":"additional","affiliation":[]},{"given":"Dennis","family":"Komm","sequence":"additional","affiliation":[]},{"given":"Beatrice","family":"Palano","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,1,8]]},"reference":[{"key":"16_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1007\/978-3-319-04298-5_9","volume-title":"SOFSEM 2014: Theory and Practice of Computer Science","author":"K Barhum","year":"2014","unstructured":"Barhum, K., B\u00f6ckenhauer, H.-J., Fori\u0161ek, M., Gebauer, H., Hromkovi\u010d, J., Krug, S., Smula, J., Steffen, B.: On the power of advice and randomization for the disjoint path allocation problem. In: Geffert, V., Preneel, B., Rovan, B., \u0160tuller, J., Tjoa, A.M. (eds.) SOFSEM 2014. LNCS, vol. 8327, pp. 89\u2013101. Springer, Heidelberg (2014)"},{"key":"16_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1007\/978-3-319-04298-5_8","volume-title":"SOFSEM 2014: Theory and Practice of Computer Science","author":"K Barhum","year":"2014","unstructured":"Barhum, K.: Tight bounds for the advice complexity of the online minimum steiner tree problem. In: Geffert, V., Preneel, B., Rovan, B., \u0160tuller, J., Tjoa, A.M. (eds.) SOFSEM 2014. LNCS, vol. 8327, pp. 77\u201388. Springer, Heidelberg (2014)"},{"key":"16_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"519","DOI":"10.1007\/978-3-642-32241-9_44","volume-title":"Computing and Combinatorics","author":"MP Bianchi","year":"2012","unstructured":"Bianchi, M.P., B\u00f6ckenhauer, H.-J., Hromkovi\u010d, J., Keller, L.: Online coloring of bipartite graphs with and without advice. In: Gudmundsson, J., Mestre, J., Viglas, T. (eds.) COCOON 2012. LNCS, vol. 7434, pp. 519\u2013530. Springer, Heidelberg (2012)"},{"key":"16_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1007\/978-3-642-38768-5_7","volume-title":"Computing and Combinatorics","author":"MP Bianchi","year":"2013","unstructured":"Bianchi, M.P., B\u00f6ckenhauer, H.-J., Hromkovi\u010d, J., Krug, S., Steffen, B.: On the advice complexity of the online L(2,1)-coloring problem on paths and cycles. In: Du, D.-Z., Zhang, G. (eds.) COCOON 2013. LNCS, vol. 7936, pp. 53\u201364. Springer, Heidelberg (2013)"},{"key":"16_CR5","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/j.tcs.2014.06.006","volume":"554","author":"H-J B\u00f6ckenhauer","year":"2014","unstructured":"B\u00f6ckenhauer, H.-J., Hromkovi\u010d, J., Komm, D., Krug, S., Smula, J., Sprock, A.: The string guessing problem as a method to prove lower bounds on the advice complexity. Theoret. Comput. Sci. 554, 95\u2013108 (2014)","journal-title":"Theoret. Comput. Sci."},{"key":"16_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1007\/978-3-642-10631-6_35","volume-title":"Algorithms and Computation","author":"H-J B\u00f6ckenhauer","year":"2009","unstructured":"B\u00f6ckenhauer, H.-J., Komm, D., Kr\u00e1lovi\u010d, R., Kr\u00e1lovi\u010d, R., M\u00f6mke, T.: On the advice complexity of online problems. In: Dong, Y., Du, D.-Z., Ibarra, O. (eds.) ISAAC 2009. LNCS, vol. 5878, pp. 331\u2013340. Springer, Heidelberg (2009)"},{"key":"16_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1007\/978-3-642-22006-7_18","volume-title":"Automata, Languages and Programming","author":"H-J B\u00f6ckenhauer","year":"2011","unstructured":"B\u00f6ckenhauer, H.-J., Komm, D., Kr\u00e1lovi\u010d, R., Kr\u00e1lovi\u010d, R.: On the advice complexity of the \n                      \n                        \n                      \n                      $$k$$\n                    -server problem. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011, Part I. LNCS, vol. 6755, pp. 207\u2013218. Springer, Heidelberg (2011)"},{"key":"16_CR8","volume-title":"Online Computation and Competitive Analysis","author":"A Borodin","year":"1998","unstructured":"Borodin, A., El-Yaniv, R.: Online Computation and Competitive Analysis. Cambridge University Press, New York (1998)"},{"unstructured":"Boyar, J., Favrholdt, L.M., Kudahl, C., Mikkelsen, J.W.: The advice complexity of a class of hard online problems. CoRR \n                      abs\/1408.7033\n                      \n                     (2014)","key":"16_CR9"},{"key":"16_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1007\/978-3-642-38016-7_2","volume-title":"Approximation and Online Algorithms","author":"S Dobrev","year":"2013","unstructured":"Dobrev, S., Kr\u00e1lovi\u010d, R., Kr\u00e1lovi\u010d, R.: Independent set with advice: the impact of graph knowledge. In: Erlebach, T., Persiano, G. (eds.) WAOA 2012. LNCS, vol. 7846, pp. 2\u201315. Springer, Heidelberg (2013)"},{"key":"16_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1007\/978-3-642-31104-8_23","volume-title":"Structural Information and Communication Complexity","author":"S Dobrev","year":"2012","unstructured":"Dobrev, S., Kr\u00e1lovi\u010d, R., Markou, E.: Online graph exploration with advice. In: Even, G., Halld\u00f3rsson, M.M. (eds.) SIROCCO 2012. LNCS, vol. 7355, pp. 267\u2013278. Springer, Heidelberg (2012)"},{"issue":"3","key":"16_CR12","first-page":"585","volume":"43","author":"S Dobrev","year":"2009","unstructured":"Dobrev, S., Kr\u00e1lovic, R., Pardubsk\u00e1, D.: Measuring the problem-relevant information in input. RAIRO ITA 43(3), 585\u2013613 (2009)","journal-title":"RAIRO ITA"},{"issue":"2","key":"16_CR13","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1109\/TIT.1975.1055349","volume":"21","author":"P Elias","year":"1975","unstructured":"Elias, P.: Universal codeword sets and representations of the integers. IEEE Trans. Inf. Theory 21(2), 194\u2013203 (1975)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"16_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1007\/978-3-642-02927-1_36","volume-title":"Automata, Languages and Programming","author":"Y Emek","year":"2009","unstructured":"Emek, Y., Fraigniaud, P., Korman, A., Ros\u00e9n, A.: Online computation with advice. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009, Part I. LNCS, vol. 5555, pp. 427\u2013438. Springer, Heidelberg (2009)"},{"key":"16_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"228","DOI":"10.1007\/978-3-642-28332-1_20","volume-title":"Language and Automata Theory and Applications","author":"M Fori\u0161ek","year":"2012","unstructured":"Fori\u0161ek, M., Keller, L., Steinov\u00e1, M.: Advice complexity of online coloring for paths. In: Dediu, A.-H., Mart\u00edn-Vide, C. (eds.) LATA 2012. LNCS, vol. 7183, pp. 228\u2013239. Springer, Heidelberg (2012)"},{"key":"16_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1007\/978-3-642-15155-2_3","volume-title":"Mathematical Foundations of Computer Science 2010","author":"J Hromkovi\u010d","year":"2010","unstructured":"Hromkovi\u010d, J., Kr\u00e1lovi\u010d, R., Kr\u00e1lovi\u010d, R.: Information complexity of online problems. In: Hlin\u011bn\u00fd, P., Ku\u010dera, A. (eds.) MFCS 2010. LNCS, vol. 6281, pp. 24\u201336. Springer, Heidelberg (2010)"},{"key":"16_CR17","volume-title":"Discrete Optimization with Interval Data: Minmax Regret and Fuzzy Approach","author":"A Kasperski","year":"2008","unstructured":"Kasperski, A.: Discrete Optimization with Interval Data: Minmax Regret and Fuzzy Approach. Springer, Heidelberg (2008)"},{"issue":"2","key":"16_CR18","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1051\/ita\/2011105","volume":"45","author":"D Komm","year":"2011","unstructured":"Komm, D., Kr\u00e1lovi\u010d, R.: Advice complexity and barely random algorithms. Theor. Inf. Appl. (RAIRO) 45(2), 249\u2013267 (2011). IEEE Computer Society","journal-title":"Theor. Inf. Appl. (RAIRO)"},{"issue":"1","key":"16_CR19","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1090\/S0002-9939-1956-0078686-7","volume":"7","author":"JB Kruskal Jr.","year":"1956","unstructured":"Kruskal Jr., J.B.: On the shortest spanning subtree of a graph and the traveling salesman problem. Proc. Am. Math. Soc. 7(1), 48\u201350 (1956)","journal-title":"Proc. Am. Math. Soc."},{"key":"16_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"689","DOI":"10.1007\/978-3-642-31594-7_58","volume-title":"Automata, Languages, and Programming","author":"N Megow","year":"2012","unstructured":"Megow, N., Skutella, M., Verschae, J., Wiese, A.: The power of recourse for online MST and TSP. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) ICALP 2012, Part I. LNCS, vol. 7391, pp. 689\u2013700. Springer, Heidelberg (2012)"},{"issue":"1","key":"16_CR21","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1017\/S096354830600770X","volume":"16","author":"J Remy","year":"2007","unstructured":"Remy, J., Souza, A., Steger, A.: On an online spanning tree problem in randomly weighted graphs. Comb. Probab. Comput. 16(1), 127\u2013144 (2007). Cambridge University Press","journal-title":"Comb. Probab. Comput."},{"key":"16_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1007\/978-3-642-38233-8_29","volume-title":"Algorithms and Complexity","author":"S Seibert","year":"2013","unstructured":"Seibert, S., Sprock, A., Unger, W.: Advice complexity of the online coloring problem. In: Spirakis, P.G., Serna, M. (eds.) CIAC 2013. LNCS, vol. 7878, pp. 345\u2013357. Springer, Heidelberg (2013)"},{"issue":"2","key":"16_CR23","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1145\/2786.2793","volume":"28","author":"DD Sleator","year":"1985","unstructured":"Sleator, D.D., Tarjan, R.E.: Amortized efficiency of list update and paging rules. Commun. ACM 28(2), 202\u2013208 (1985)","journal-title":"Commun. ACM"},{"issue":"4","key":"16_CR24","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1016\/0020-0190(93)90142-V","volume":"48","author":"Y Teh Tsai","year":"1993","unstructured":"Teh Tsai, Y., Yi Tang, C.: The competitiveness of randomized algorithms for on-line Steiner tree and on-line spanning tree problems. Inf. Process. Lett. 48(4), 177\u2013182 (1993). Elsevier","journal-title":"Inf. Process. Lett."}],"container-title":["Lecture Notes in Computer Science","SOFSEM 2016: Theory and Practice of Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-49192-8_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,1]],"date-time":"2019-06-01T09:08:02Z","timestamp":1559380082000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-49192-8_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783662491911","9783662491928"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-49192-8_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}