{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,7]],"date-time":"2025-08-07T20:26:52Z","timestamp":1754598412586,"version":"3.41.0"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2018,6,25]],"date-time":"2018-06-25T00:00:00Z","timestamp":1529884800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2018,6,25]],"date-time":"2018-06-25T00:00:00Z","timestamp":1529884800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"crossref","award":["12H00855","17K12635"],"award-info":[{"award-number":["12H00855","17K12635"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100009024","name":"Exploratory Research for Advanced Technology","doi-asserted-by":"publisher","award":["JPMJER1201"],"award-info":[{"award-number":["JPMJER1201"]}],"id":[{"id":"10.13039\/501100009024","id-type":"DOI","asserted-by":"publisher"}]},{"name":"ETH","award":["Postdoctoral Fellowship"],"award-info":[{"award-number":["Postdoctoral Fellowship"]}]},{"DOI":"10.13039\/501100002790","name":"Canadian Network for Research and Innovation in Machining Technology, Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100002790","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100008095","name":"Carleton University","doi-asserted-by":"crossref","award":["postdoctoral award"],"award-info":[{"award-number":["postdoctoral award"]}],"id":[{"id":"10.13039\/100008095","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100002661","name":"Fonds De La Recherche Scientifique - FNRS","doi-asserted-by":"crossref","award":["Directeur de Recherches"],"award-info":[{"award-number":["Directeur de Recherches"]}],"id":[{"id":"10.13039\/501100002661","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2019,4]]},"DOI":"10.1007\/s00453-018-0473-y","type":"journal-article","created":{"date-parts":[[2018,6,25]],"date-time":"2018-06-25T13:45:04Z","timestamp":1529934304000},"page":"1319-1341","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Dynamic Graph Coloring"],"prefix":"10.1007","volume":"81","author":[{"given":"Luis","family":"Barba","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jean","family":"Cardinal","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Matias","family":"Korman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stefan","family":"Langerman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andr\u00e9","family":"van Renssen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marcel","family":"Roeloffzen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sander","family":"Verdonschot","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,6,25]]},"reference":[{"key":"473_CR1","doi-asserted-by":"crossref","unstructured":"Barba, L., Cardinal, J., Korman, M., Langerman, S., van Renssen, A., Roeloffzen, M., Verdonschot, S.: Dynamic graph coloring. In: 15th Alg. Data Structures Symp., Lecture Notes in Comput. Sci., vol. 10389, pp. 97\u2013108 (2017)","DOI":"10.1007\/978-3-319-62127-2_9"},{"issue":"1","key":"473_CR2","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1137\/130914140","volume":"44","author":"S Baswana","year":"2015","unstructured":"Baswana, S., Gupta, M., Sen, S.: Fully dynamic maximal matching in $${O}(\\log n)$$ update time. SIAM J. Comput. 44(1), 88\u2013113 (2015)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"473_CR3","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1145\/2344422.2344425","volume":"8","author":"S Baswana","year":"2012","unstructured":"Baswana, S., Khurana, S., Sarkar, S.: Fully dynamic randomized algorithms for graph spanners. ACM Trans. Algorithms 8(4), 35 (2012)","journal-title":"ACM Trans. Algorithms"},{"issue":"4","key":"473_CR4","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1016\/0196-6774(80)90015-2","volume":"1","author":"JL Bentley","year":"1980","unstructured":"Bentley, J.L., Saxe, J.B.: Decomposable searching problems I: static-to-dynamic transformation. J. Algorithms 1(4), 301\u2013358 (1980)","journal-title":"J. Algorithms"},{"issue":"2","key":"473_CR5","doi-asserted-by":"crossref","first-page":"105","DOI":"10.3233\/FI-2012-620","volume":"114","author":"P Borowiecki","year":"2012","unstructured":"Borowiecki, P., Sidorowicz, E.: Dynamic coloring of graphs. Fundam. Inf. 114(2), 105\u2013128 (2012)","journal-title":"Fundam. Inf."},{"key":"473_CR6","doi-asserted-by":"publisher","unstructured":"Coudert, O.: Exact coloring of real-life graphs is easy. In: Proceedings of 34th Design Automation Conference. ACM, pp. 121\u2013126 (1997). https:\/\/doi.org\/10.1145\/266021.266047","DOI":"10.1145\/266021.266047"},{"key":"473_CR7","volume-title":"Algorithms and Theory of Computation Handbook","author":"C Demetrescu","year":"2010","unstructured":"Demetrescu, C., Eppstein, D., Galil, Z., Italiano, G.F.: Dynamic graph algorithms. In: Atallah, M.J., Blanton, M. (eds.) Algorithms and Theory of Computation Handbook. CRC Press, Boca Raton (2010)"},{"key":"473_CR8","volume-title":"Handbook on Data Structures and Applications, Computer and Information Science","author":"C Demetrescu","year":"2005","unstructured":"Demetrescu, C., Finocchi, I., Italiano, P.: Dynamic graphs. In: Mehta, D., Sahni, S. (eds.) Handbook on Data Structures and Applications, Computer and Information Science. CRC Press, Boca Raton (2005)"},{"key":"473_CR9","unstructured":"Dutot, A., Guinand, F., Olivier, D., Pign\u00e9, Y.: On the decentralized dynamic graph-coloring problem. In: Proc. Worksh. Compl. Sys. and Self-Org. Mod. (2007)"},{"issue":"2","key":"473_CR10","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1006\/jagm.1996.0836","volume":"23","author":"MM Halld\u00f3rsson","year":"1997","unstructured":"Halld\u00f3rsson, M.M.: Parallel and on-line graph coloring. J. Algorithms 23(2), 265\u2013280 (1997)","journal-title":"J. Algorithms"},{"issue":"1","key":"473_CR11","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/0304-3975(94)90157-0","volume":"130","author":"MM Halldrsson","year":"1994","unstructured":"Halldrsson, M.M., Szegedy, M.: Lower bounds for on-line graph coloring. Theor. Comput. Sci. 130(1), 163\u2013174 (1994)","journal-title":"Theor. Comput. Sci."},{"key":"473_CR12","doi-asserted-by":"crossref","unstructured":"Henzinger, M., Krinninger, S., Nanongkai, D.: A subquadratic-time algorithm for decremental single-source shortest paths. In: Proc. 25th ACM-SIAM Symp. on Discr. Alg., pp. 1053\u20131072 (2014)","DOI":"10.1137\/1.9781611973402.79"},{"issue":"4","key":"473_CR13","doi-asserted-by":"publisher","first-page":"723","DOI":"10.1145\/502090.502095","volume":"48","author":"J Holm","year":"2001","unstructured":"Holm, J., De Lichtenberg, K., Thorup, M.: Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. J. ACM 48(4), 723\u2013760 (2001)","journal-title":"J. ACM"},{"key":"473_CR14","doi-asserted-by":"crossref","unstructured":"Kapron, B.M., King, V., Mountjoy, B.: Dynamic graph connectivity in polylogarithmic worst case time. In: Proc. 24th ACM-SIAM Symp. on Discr. Alg., pp. 1131\u20131142 (2013)","DOI":"10.1137\/1.9781611973105.81"},{"key":"473_CR15","doi-asserted-by":"crossref","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W., Bohlinger, J.D. (eds.) Complexity of Computer Computations, pp. 85\u2013103. Plenum, New York (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"issue":"1\u20133","key":"473_CR16","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1016\/0012-365X(89)90096-4","volume":"75","author":"L Lov\u00e1sz","year":"1989","unstructured":"Lov\u00e1sz, L., Saks, M.E., Trotter, W.T.: An on-line graph coloring algorithm with sublinear performance ratio. Discrete Math. 75(1\u20133), 319\u2013325 (1989)","journal-title":"Discrete Math."},{"issue":"2","key":"473_CR17","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1002\/net.3230250205","volume":"25","author":"MV Marathe","year":"1995","unstructured":"Marathe, M.V., Breu, H., Hunt III, H.B., Ravi, S.S., Rosenkrantz, D.J.: Simple heuristics for unit disk graphs. Networks 25(2), 59\u201368 (1995). https:\/\/doi.org\/10.1002\/net.3230250205","journal-title":"Networks"},{"key":"473_CR18","doi-asserted-by":"crossref","unstructured":"Ouerfelli, L., Bouziri, H.: Greedy algorithms for dynamic graph coloring. In: Proc. Int. Conf. on Comm., Comp. and Control App., pp. 1\u20135 (2011)","DOI":"10.1109\/CCCA.2011.6031437"},{"issue":"4","key":"473_CR19","doi-asserted-by":"publisher","first-page":"168","DOI":"10.1016\/0020-0190(81)90093-4","volume":"12","author":"MH Overmars","year":"1981","unstructured":"Overmars, M.H., van Leeuwen, J.: Worst-case optimal insertion and deletion methods for decomposable searching problems. Inf. Process. Lett. 12(4), 168\u2013173 (1981)","journal-title":"Inf. Process. Lett."},{"key":"473_CR20","unstructured":"Preuveneers, D., Berbers, Y.: ACODYGRA: an agent algorithm for coloring dynamic graphs. In: Symb. Num. Alg. Sci. Comp., pp. 381\u2013390 (2004)"},{"key":"473_CR21","doi-asserted-by":"crossref","unstructured":"Roditty, L., Zwick, U.: Improved dynamic reachability algorithms for directed graphs. In: Proc. 43rd IEEE Sym. Found. Comp. Sci., pp. 679\u2013688 (2002)","DOI":"10.1109\/SFCS.2002.1181993"},{"key":"473_CR22","doi-asserted-by":"crossref","unstructured":"Roditty, L., Zwick, U.: Dynamic approximate all-pairs shortest paths in undirected graphs. In: Proc. 45th IEEE Sym. Found. Comp. Sci., pp. 499\u2013508 (2004)","DOI":"10.1109\/FOCS.2004.22"},{"key":"473_CR23","doi-asserted-by":"crossref","unstructured":"Saxe, J.B., Bentley, J.L.: Transforming static data structures to dynamic structures (abridged version). In: Proc. 20th Symp. Found. Comp. Sci., pp. 148\u2013168 (1979)","DOI":"10.1109\/SFCS.1979.47"},{"issue":"1","key":"473_CR24","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1007\/s00493-007-0045-2","volume":"27","author":"M Thorup","year":"2007","unstructured":"Thorup, M.: Fully-dynamic min-cut. Combinatorica 27(1), 91\u2013127 (2007)","journal-title":"Combinatorica"},{"issue":"4","key":"473_CR25","doi-asserted-by":"publisher","first-page":"657","DOI":"10.1016\/0196-6774(92)90061-G","volume":"13","author":"S Vishwanathan","year":"1992","unstructured":"Vishwanathan, S.: Randomized online graph coloring. J. Algorithms 13(4), 657\u2013669 (1992)","journal-title":"J. Algorithms"},{"key":"473_CR26","doi-asserted-by":"publisher","first-page":"103","DOI":"10.4086\/toc.2007.v003a006","volume":"3","author":"D Zuckerman","year":"2007","unstructured":"Zuckerman, D.: Linear degree extractors and the inapproximability of max clique and chromatic number. Theory Comput. 3, 103\u2013128 (2007). https:\/\/doi.org\/10.4086\/toc.2007.v003a006","journal-title":"Theory Comput."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0473-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-018-0473-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0473-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,5]],"date-time":"2025-07-05T09:05:45Z","timestamp":1751706345000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-018-0473-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,6,25]]},"references-count":26,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2019,4]]}},"alternative-id":["473"],"URL":"https:\/\/doi.org\/10.1007\/s00453-018-0473-y","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2018,6,25]]},"assertion":[{"value":"29 August 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 June 2018","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 June 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}