{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,9]],"date-time":"2025-04-09T17:13:56Z","timestamp":1744218836245,"version":"3.37.3"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2022,10,19]],"date-time":"2022-10-19T00:00:00Z","timestamp":1666137600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2022,10,19]],"date-time":"2022-10-19T00:00:00Z","timestamp":1666137600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2023,4]]},"DOI":"10.1007\/s00453-022-01050-7","type":"journal-article","created":{"date-parts":[[2022,10,20]],"date-time":"2022-10-20T11:06:51Z","timestamp":1666264011000},"page":"854-878","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Trade-Offs in Dynamic Coloring for Bipartite and General Graphs"],"prefix":"10.1007","volume":"85","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5727-5406","authenticated-orcid":false,"given":"Manas Jyoti","family":"Kashyop","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"N. S.","family":"Narayanaswamy","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Meghana","family":"Nasre","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sai Mohith","family":"Potluri","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,10,19]]},"reference":[{"key":"1050_CR1","doi-asserted-by":"crossref","unstructured":"Assadi, S., Onak, K., Schieber, B., Solomon, S.: Fully dynamic maximal independent set with sublinear update time. In: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, pp. 815\u2013826 (2018)","DOI":"10.1145\/3188745.3188922"},{"key":"1050_CR2","doi-asserted-by":"crossref","unstructured":"Barba, L., Cardinal, J., Korman, M., Langerman, S., Renssen, A.V., Roeloffzen, M., Verdonschot, S.: Dynamic graph coloring. In: Algorithms and Data Structures\u201415th International Symposium, WADS 2017, pp. 97\u2013108 (2017)","DOI":"10.1007\/978-3-319-62127-2_9"},{"key":"1050_CR3","doi-asserted-by":"crossref","unstructured":"Bhattacharya, S., Chakrabarty, D., Henzinger, M., Nanongkai, D.: Dynamic algorithms for graph coloring. In: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, pp. 1\u201320 (2018)","DOI":"10.1137\/1.9781611975031.1"},{"key":"1050_CR4","unstructured":"Bhattacharya, S., Grandoni, F., Kulkarni, J., Liu, Q.C., Solomon, S.: Fully dynamic ($$\\Delta $$+1)-coloring in constant update time. CoRR. arXiv:1910.02063 (2019)"},{"key":"1050_CR5","doi-asserted-by":"crossref","unstructured":"Brodal, G.S., Fagerberg, R.: Dynamic representation of sparse graphs. In: Algorithms and Data Structures, 6th International Workshop, WADS, pp. 342\u2013351 (1999)","DOI":"10.1007\/3-540-48447-7_34"},{"key":"1050_CR6","first-page":"1180","volume-title":"Introduction to Algorithms, Appendix B","author":"TH Cormen","year":"2009","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, Appendix B, 3rd edn., pp. 1180\u20131181. The MIT Press, Cambridge (2009)","edition":"3"},{"key":"1050_CR7","doi-asserted-by":"crossref","unstructured":"Fredman, M., Saks, M.: The cell probe complexity of dynamic data structures. In: Proceedings of the Twenty-first Annual ACM Symposium on Theory of Computing, STOC \u201989 (1989)","DOI":"10.1145\/73007.73040"},{"key":"1050_CR8","doi-asserted-by":"crossref","unstructured":"Fredman, M.L., Willard, D.E.: BLASTING through the information theoretic barrier with FUSION TREES. In: Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, pp. 1\u20137. ACM (1990)","DOI":"10.1145\/100216.100217"},{"key":"1050_CR9","doi-asserted-by":"crossref","unstructured":"Henzinger, M.R., King, V.: Randomized dynamic graph algorithms with polylogarithmic time per operation. In: Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, pp. 519\u2013527 (1995)","DOI":"10.1145\/225058.225269"},{"key":"1050_CR10","doi-asserted-by":"crossref","unstructured":"Henzinger, M., Peng, P.: Constant-time dynamic ($$\\Delta 1$$)-coloring. In: 37th International Symposium on Theoretical Aspects of Computer Science, STACS 2020, pp. 53:1\u201353:18 (2020)","DOI":"10.1145\/3501403"},{"key":"1050_CR11","unstructured":"Henzinger, M., Neumann, S., Wiese, A.: Explicit and implicit dynamic coloring of graphs with bounded arboricity. CoRR (2020)"},{"issue":"4","key":"1050_CR12","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":"1050_CR13","unstructured":"Kashyop, M.J., Narayanaswamy, N.S., Nasre, M., Potluri, S.M.: Dynamic coloring for bipartite and general graphs. CoRR. arXiv:1909.07854 (2019)"},{"issue":"1\u20133","key":"1050_CR14","doi-asserted-by":"publisher","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."},{"key":"1050_CR15","unstructured":"Miltersen, P.B. Cell probe complexity\u2014a survey. In: In 19th Conference on the Foundations of Software Technology and Theoretical Computer Science (FSTTCS), 1999. Advances in Data Structures Workshop (1999)"},{"issue":"1","key":"1050_CR16","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1112\/jlms\/s1-39.1.12","volume":"s1\u201339","author":"CSJA Nash-Williams","year":"1964","unstructured":"Nash-Williams, C.S.J.A.: Decomposition of finite graphs into forests. J. Lond. Math. Soc. s1\u201339(1), 12 (1964)","journal-title":"J. Lond. Math. Soc."},{"key":"1050_CR17","doi-asserted-by":"crossref","unstructured":"Neiman, O., Solomon, S.: Simple deterministic algorithms for fully dynamic maximal matching. In: Symposium on Theory of Computing Conference, STOC\u201913, pp. 745\u2013754 (2013)","DOI":"10.1145\/2488608.2488703"},{"key":"1050_CR18","unstructured":"P\u01cetra\u015fcu, M.: Unifying the landscape of cell-probe lower bounds. CoRR. arXiv:1010.3783"},{"issue":"4","key":"1050_CR19","doi-asserted-by":"publisher","first-page":"932","DOI":"10.1137\/S0097539705447256","volume":"35","author":"M P\u01cetra\u015fcu","year":"2006","unstructured":"P\u01cetra\u015fcu, M., Demaine, E.D.: Logarithmic lower bounds in the cell-probe model. SIAM J. Comput. 35(4), 932\u2013963 (2006)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"1050_CR20","doi-asserted-by":"publisher","first-page":"362","DOI":"10.1016\/0022-0000(83)90006-5","volume":"26","author":"DD Sleator","year":"1983","unstructured":"Sleator, D.D., Tarjan, R.E.: A data structure for dynamic trees. J. Comput. Syst. Sci. 26(3), 362\u2013391 (1983)","journal-title":"J. Comput. Syst. Sci."},{"key":"1050_CR21","doi-asserted-by":"crossref","unstructured":"Solomon, S.: Fully dynamic maximal matching in constant update time. In: IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, pp. 325\u2013334 (2016)","DOI":"10.1109\/FOCS.2016.43"},{"key":"1050_CR22","unstructured":"Solomon, S., Wein, N.: Improved dynamic graph coloring. In: 26th Annual European Symposium on Algorithms, ESA 2018, pp. 72:1\u201372:16 (2018)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-01050-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-022-01050-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-01050-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,3,29]],"date-time":"2023-03-29T13:12:31Z","timestamp":1680095551000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-022-01050-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,10,19]]},"references-count":22,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,4]]}},"alternative-id":["1050"],"URL":"https:\/\/doi.org\/10.1007\/s00453-022-01050-7","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2022,10,19]]},"assertion":[{"value":"19 May 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 October 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 October 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}