{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,10]],"date-time":"2026-02-10T16:33:01Z","timestamp":1770741181717,"version":"3.49.0"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2018,9,25]],"date-time":"2018-09-25T00:00:00Z","timestamp":1537833600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100008394","name":"Natur og Univers, Det Frie Forskningsr\u00e5d","doi-asserted-by":"publisher","award":["DFF-1323-00247"],"award-info":[{"award-number":["DFF-1323-00247"]}],"id":[{"id":"10.13039\/100008394","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100008394","name":"Natur og Univers, Det Frie Forskningsr\u00e5d","doi-asserted-by":"publisher","award":["DFF-7014-00041"],"award-info":[{"award-number":["DFF-7014-00041"]}],"id":[{"id":"10.13039\/100008394","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100008398","name":"Villum Fonden","doi-asserted-by":"publisher","award":["VKR023219"],"award-info":[{"award-number":["VKR023219"]}],"id":[{"id":"10.13039\/100008398","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2019,5]]},"DOI":"10.1007\/s00453-018-0519-1","type":"journal-article","created":{"date-parts":[[2018,9,25]],"date-time":"2018-09-25T14:55:40Z","timestamp":1537887340000},"page":"1938-1964","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["Online Dominating Set"],"prefix":"10.1007","volume":"81","author":[{"given":"Joan","family":"Boyar","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stephan J.","family":"Eidenbenz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lene M.","family":"Favrholdt","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michal","family":"Kotrb\u010d\u00edk","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kim S.","family":"Larsen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,9,25]]},"reference":[{"issue":"4","key":"519_CR1","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1007\/s00453-001-0116-5","volume":"33","author":"J Alber","year":"2002","unstructured":"Alber, J., Bodlaender, H.L., Fernau, H., Kloks, T., Niedermeier, R.: Fixed parameter algorithms for dominating set and related problems on planar graphs. Algorithmica 33(4), 461\u2013493 (2002)","journal-title":"Algorithmica"},{"issue":"1","key":"519_CR2","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1145\/174644.174650","volume":"41","author":"BS Baker","year":"1994","unstructured":"Baker, B.S.: Approximation algorithms for NP-complete problems on planar graphs. J. ACM 41(1), 153\u2013180 (1994)","journal-title":"J. ACM"},{"key":"519_CR3","volume-title":"Theory of Graphs and its Applications","author":"C Berge","year":"1962","unstructured":"Berge, C.: Theory of Graphs and its Applications. Meuthen, London (1962)"},{"key":"519_CR4","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1007\/978-3-319-18263-6_4","volume-title":"12th International Workshop on Approximation and Online Algorithms (WAOA), Lecture Notes in Computer Science","author":"M B\u00f6hm","year":"2015","unstructured":"B\u00f6hm, M., Sgall, J., Vesel\u00fd, P.: Online colored bin packing. In: Bampis, E., Svensson, O. (eds.) 12th International Workshop on Approximation and Online Algorithms (WAOA), Lecture Notes in Computer Science, vol. 8952, pp. 35\u201346. Springer, Berlin (2015)"},{"key":"519_CR5","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, Cambridge (1998)"},{"issue":"4","key":"519_CR6","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1007\/PL00009286","volume":"25","author":"J Boyar","year":"1999","unstructured":"Boyar, J., Larsen, K.S.: The seat reservation problem. Algorithmica 25(4), 403\u2013417 (1999)","journal-title":"Algorithmica"},{"key":"519_CR7","first-page":"263","volume-title":"19th Annual European Symposium on Algorithms (ESA), Lecture Notes in Computer Science","author":"M Chrobak","year":"2011","unstructured":"Chrobak, M., Sgall, J., Woeginger, G.J.: Two-bounded-space bin packing revisited. In: Demetrescu, C., Halld\u00f3rsson, M.M. (eds.) 19th Annual European Symposium on Algorithms (ESA), Lecture Notes in Computer Science, vol. 6942, pp. 263\u2013274. Springer, Berlin (2011)"},{"issue":"3","key":"519_CR8","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1287\/moor.4.3.233","volume":"4","author":"V Chv\u00e1tal","year":"1979","unstructured":"Chv\u00e1tal, V.: A greedy heuristic for the set-covering problem. Math. Oper. Res. 4(3), 233\u2013235 (1979)","journal-title":"Math. Oper. Res."},{"key":"519_CR9","first-page":"376","volume":"1","author":"B Das","year":"1997","unstructured":"Das, B., Bharghavan, V.: Routing in ad-hoc networks using minimum connected dominating sets. IEEE Int. Conf. Commun. 1, 376\u2013380 (1997)","journal-title":"IEEE Int. Conf. Commun."},{"issue":"4","key":"519_CR10","doi-asserted-by":"publisher","first-page":"873","DOI":"10.1137\/S0097539792228228","volume":"24","author":"RG Downey","year":"1995","unstructured":"Downey, R.G., Fellows, M.R.: Fixed-parameter tractability and completeness I: basic results. SIAM J. Comput. 24(4), 873\u2013921 (1995)","journal-title":"SIAM J. Comput."},{"key":"519_CR11","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4614-5242-3","volume-title":"Connected Dominating Set: Theory and Applications","author":"DZ Du","year":"2013","unstructured":"Du, D.Z., Wan, P.J.: Connected Dominating Set: Theory and Applications. Springer, New York (2013)"},{"issue":"4","key":"519_CR12","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U Feige","year":"1998","unstructured":"Feige, U.: A threshold of $$\\ln n$$ ln n for approximating set cover. J. ACM 45(4), 634\u2013652 (1998)","journal-title":"J. ACM"},{"key":"519_CR13","volume-title":"Fundamentals of Domination in Graphs","author":"TW Haynes","year":"1998","unstructured":"Haynes, T.W., Hedetniemi, S., Slater, P.: Fundamentals of Domination in Graphs. Marcel Dekker, New York (1998)"},{"key":"519_CR14","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4614-6525-6","volume-title":"Total Domination in Graphs","author":"M Henning","year":"2013","unstructured":"Henning, M., Yao, A.: Total Domination in Graphs. Springer, New York (2013)"},{"key":"519_CR15","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1007\/BF01762111","volume":"3","author":"AR Karlin","year":"1988","unstructured":"Karlin, A.R., Manasse, M.S., Rudolph, L., Sleator, D.D.: Competitive snoopy caching. Algorithmica 3, 79\u2013119 (1988)","journal-title":"Algorithmica"},{"key":"519_CR16","series-title":"The IBM Research Symposia Series","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"RM Karp","year":"1972","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (eds.) Complexity of Computer Computations. The IBM Research Symposia Series, pp. 85\u2013103. Plenum Press, New York (1972)"},{"issue":"1","key":"519_CR17","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/S0020-0190(96)00191-3","volume":"61","author":"GH King","year":"1997","unstructured":"King, G.H., Tzeng, W.G.: On-line algorithms for the dominating set problem. Inf. Process. Lett. 61(1), 11\u201314 (1997)","journal-title":"Inf. Process. Lett."},{"key":"519_CR18","volume-title":"Theorie der Endlichen und Unendlichen Graphen","author":"D K\u00f6nig","year":"1950","unstructured":"K\u00f6nig, D.: Theorie der Endlichen und Unendlichen Graphen. Chelsea, New York (1950)"},{"key":"519_CR19","volume-title":"Introduction to Combinatorial Mathematics","author":"CL Liu","year":"1968","unstructured":"Liu, C.L.: Introduction to Combinatorial Mathematics. McGraw-Hill, New York (1968)"},{"key":"519_CR20","doi-asserted-by":"crossref","unstructured":"Ore, O.: Theory of graphs. In: Colloquium Publications, vol. 38, American Mathematical Society, Providence (1962)","DOI":"10.1090\/coll\/038"},{"issue":"2","key":"519_CR21","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"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0519-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-018-0519-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0519-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,5]],"date-time":"2023-09-05T11:06:46Z","timestamp":1693912006000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-018-0519-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,9,25]]},"references-count":21,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2019,5]]}},"alternative-id":["519"],"URL":"https:\/\/doi.org\/10.1007\/s00453-018-0519-1","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,9,25]]},"assertion":[{"value":"9 June 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 September 2018","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 September 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}