{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,22]],"date-time":"2025-10-22T23:10:38Z","timestamp":1761174638221},"publisher-location":"Berlin, Heidelberg","reference-count":12,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642330896"},{"type":"electronic","value":"9783642330902"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-33090-2_12","type":"book-chapter","created":{"date-parts":[[2012,8,28]],"date-time":"2012-08-28T11:29:11Z","timestamp":1346153351000},"page":"121-132","source":"Crossref","is-referenced-by-count":7,"title":["On Online Labeling with Polynomially Many Labels"],"prefix":"10.1007","author":[{"given":"Martin","family":"Babka","sequence":"first","affiliation":[]},{"given":"Jan","family":"Bul\u00e1nek","sequence":"additional","affiliation":[]},{"given":"Vladim\u00edr","family":"\u010cun\u00e1t","sequence":"additional","affiliation":[]},{"given":"Michal","family":"Kouck\u00fd","sequence":"additional","affiliation":[]},{"given":"Michael","family":"Saks","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"doi-asserted-by":"crossref","unstructured":"Bul\u00e1nek, J., Kouck\u00fd, M., Saks, M.: Tight lower bounds for the online labeling problem. In: Karloff, H.J., Pitassi, T. (eds.) Proc. of 66th Symp. of Theory of Computation (STOC 2012), pp. 1185\u20131198. ACM (2012)","key":"12_CR1","DOI":"10.1145\/2213977.2214083"},{"key":"12_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"152","DOI":"10.1007\/3-540-45749-6_17","volume-title":"Algorithms - ESA 2002","author":"M.A. Bender","year":"2002","unstructured":"Bender, M.A., Cole, R., Demaine, E.D., Farach-Colton, M., Zito, J.: Two Simplified Algorithms for Maintaining Order in a List. In: M\u00f6hring, R.H., Raman, R. (eds.) ESA 2002. LNCS, vol.\u00a02461, pp. 152\u2013164. Springer, Heidelberg (2002)"},{"issue":"2","key":"12_CR3","first-page":"341","volume":"35","author":"M.A. Bender","year":"2005","unstructured":"Bender, M.A., Demaine, E.D., Farach-Colton, M.: Cache-oblivious b-trees. Journal on Computing\u00a035(2), 341\u2013358 (2005)","journal-title":"Journal on Computing"},{"issue":"2","key":"12_CR4","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1016\/j.jalgor.2004.04.014","volume":"53","author":"M.A. Bender","year":"2004","unstructured":"Bender, M.A., Duan, Z., Iacono, J., Wu, J.: A locality-preserving cache-oblivious dynamic dictionary. Journal of Algorithms\u00a053(2), 115\u2013136 (2004)","journal-title":"Journal of Algorithms"},{"doi-asserted-by":"crossref","unstructured":"Brodal, G.S., Fagerberg, R., Jacob, R.: Cache oblivious search trees via binary trees of small height. In: Eppstein, D. (ed.) Proc. of 13th ACM-SIAM Symp. on Discrete Algorithms. SODA, pp. 39\u201348. ACM\/SIAM (2002)","key":"12_CR5","DOI":"10.7146\/brics.v8i36.21696"},{"issue":"1","key":"12_CR6","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/j.ipl.2006.07.011","volume":"101","author":"R.S. Bird","year":"2007","unstructured":"Bird, R.S., Sadnicki, S.: Minimal on-line labelling. Information Processing Letters\u00a0101(1), 41\u201345 (2007)","journal-title":"Information Processing Letters"},{"issue":"3","key":"12_CR7","doi-asserted-by":"publisher","first-page":"626","DOI":"10.1137\/S0895480100315808","volume":"18","author":"P.F. Dietz","year":"2004","unstructured":"Dietz, P.F., Seiferas, J.I., Zhang, J.: A tight lower bound for online monotonic list labeling. SIAM J. Discrete Mathematics\u00a018(3), 626\u2013637 (2004)","journal-title":"SIAM J. Discrete Mathematics"},{"issue":"3-4","key":"12_CR8","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1007\/s00446-010-0119-z","volume":"24","author":"Y. Emek","year":"2011","unstructured":"Emek, Y., Korman, A.: New bounds for the controller problem. Distributed Computing\u00a024(3-4), 177\u2013186 (2011)","journal-title":"Distributed Computing"},{"key":"12_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"417","DOI":"10.1007\/3-540-10843-2_34","volume-title":"Automata, Languages and Programming","author":"A. Itai","year":"1981","unstructured":"Itai, A., Konheim, A.G., Rodeh, M.: A Sparse Table Implementation of Priority Queues. In: Even, S., Kariv, O. (eds.) ICALP 1981. LNCS, vol.\u00a0115, pp. 417\u2013431. Springer, Heidelberg (1981)"},{"issue":"2","key":"12_CR10","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1016\/0890-5401(92)90034-D","volume":"97","author":"D.E. Willard","year":"1992","unstructured":"Willard, D.E.: A density control algorithm for doing insertions and deletions in a sequentially ordered file in good worst-case time. Information and Computation\u00a097(2), 150\u2013204 (1992)","journal-title":"Information and Computation"},{"unstructured":"Zhang, J.: Density Control and On-Line Labeling Problems. PhD thesis, University of Rochester (1993)","key":"12_CR11"},{"doi-asserted-by":"crossref","unstructured":"Babka, M., Bul\u00e1nek, J., \u010cun\u00e1t, V., Kouck\u00fd, M., Saks, M.: On Online Labeling with Superlinearly Many Labels (2012) (manuscript)","key":"12_CR12","DOI":"10.1007\/978-3-642-33090-2_12"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2012"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-33090-2_12.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T07:54:43Z","timestamp":1620114883000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-33090-2_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642330896","9783642330902"],"references-count":12,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-33090-2_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}