{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:53:38Z","timestamp":1781078018306,"version":"3.54.1"},"publisher-location":"Cham","reference-count":27,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319084039","type":"print"},{"value":"9783319084046","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-08404-6_21","type":"book-chapter","created":{"date-parts":[[2014,6,25]],"date-time":"2014-06-25T03:55:08Z","timestamp":1403668508000},"page":"241-252","source":"Crossref","is-referenced-by-count":9,"title":["Fast Dynamic Graph Algorithms for Parameterized Problems"],"prefix":"10.1007","author":[{"given":"Yoichi","family":"Iwata","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Keigo","family":"Oka","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"21_CR1","doi-asserted-by":"crossref","unstructured":"Boral, A., Cygan, M., Kociumaka, T., Pilipczuk, M.: Fast branching algorithm for cluster vertex deletion. CoRR, abs\/1306.3877 (2013)","DOI":"10.1007\/978-3-319-06686-8_9"},{"issue":"40-42","key":"21_CR2","doi-asserted-by":"publisher","first-page":"3736","DOI":"10.1016\/j.tcs.2010.06.026","volume":"411","author":"J. Chen","year":"2010","unstructured":"Chen, J., Kanj, I.A., Xia, G.: Improved upper bounds for vertex cover. Theor. Comput. Sci.\u00a0411(40-42), 3736\u20133756 (2010)","journal-title":"Theor. Comput. Sci."},{"key":"21_CR3","doi-asserted-by":"crossref","unstructured":"Demetrescu, C., Italiano, G.F.: Fully dynamic transitive closure: Breaking through the o(n2) barrier. In: FOCS, pp. 381\u2013389 (2000)","DOI":"10.1109\/SFCS.2000.892126"},{"key":"21_CR4","doi-asserted-by":"crossref","unstructured":"Demetrescu, C., Italiano, G.F.: A new approach to dynamic all pairs shortest paths. In: STOC, pp. 159\u2013166 (2003)","DOI":"10.1145\/780542.780567"},{"issue":"1","key":"21_CR5","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/0022-0000(89)90034-2","volume":"38","author":"J.R. Driscoll","year":"1989","unstructured":"Driscoll, J.R., Sarnak, N., Sleator, D.D., Tarjan, R.E.: Making data structures persistent. J. Comput. Syst. Sci.\u00a038(1), 86\u2013124 (1989)","journal-title":"J. Comput. Syst. Sci."},{"key":"21_CR6","unstructured":"Dvorak, Z., Kupec, M., Tuma, V.: Dynamic data structure for tree-depth decomposition. CoRR, abs\/1307.2863 (2013)"},{"key":"21_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"304","DOI":"10.1007\/978-3-642-40104-6_27","volume-title":"Algorithms and Data Structures","author":"Z. Dvo\u0159\u00e1k","year":"2013","unstructured":"Dvo\u0159\u00e1k, Z., T\u016fma, V.: A dynamic data structure for counting subgraphs in sparse graphs. In: Dehne, F., Solis-Oba, R., Sack, J.-R. (eds.) WADS 2013. LNCS, vol.\u00a08037, pp. 304\u2013315. Springer, Heidelberg (2013)"},{"key":"21_CR8","doi-asserted-by":"crossref","unstructured":"Eppstein, D., Galil, Z., Italiano, G.F., Nissenzweig, A.: Sparsification-a technique for speeding up dynamic graph algorithms (extended abstract). In: FOCS, pp. 60\u201369 (1992)","DOI":"10.1109\/SFCS.1992.267818"},{"key":"21_CR9","unstructured":"Gary, M.R., Johnson, D.S.: Computers and intractability: A guide to the theory of np-completeness (1979)"},{"key":"21_CR10","doi-asserted-by":"crossref","unstructured":"Henzinger, M.R., King, V.: Randomized dynamic graph algorithms with polylogarithmic time per operation. In: STOC, pp. 519\u2013527 (1995)","DOI":"10.1145\/225058.225269"},{"issue":"4","key":"21_CR11","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\u00a048(4), 723\u2013760 (2001)","journal-title":"J. ACM"},{"issue":"1","key":"21_CR12","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1007\/s00224-008-9150-x","volume":"47","author":"F. H\u00fcffner","year":"2010","unstructured":"H\u00fcffner, F., Komusiewicz, C., Moser, H., Niedermeier, R.: Fixed-parameter algorithms for cluster vertex deletion. Theory Comput. Syst.\u00a047(1), 196\u2013217 (2010)","journal-title":"Theory Comput. Syst."},{"key":"21_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"212","DOI":"10.1007\/3-540-57273-2_57","volume-title":"Algorithms - ESA \u201993","author":"G.F. Italiano","year":"1993","unstructured":"Italiano, G.F., Poutr\u00e9, J.A.L., Rauch, M.H.: Fully dynamic planarity testing in planar embedded graphs (extended abstract). In: Lengauer, T. (ed.) ESA 1993. LNCS, vol.\u00a0726, pp. 212\u2013223. Springer, Heidelberg (1993)"},{"key":"21_CR14","doi-asserted-by":"crossref","unstructured":"Iwata, Y., Oka, K.: Fast dynamic graph algorithms for parameterized problems (2014) (manuscript)","DOI":"10.1007\/978-3-319-08404-6_21"},{"key":"21_CR15","doi-asserted-by":"crossref","unstructured":"Patrascu, M., Demaine, E.D.: Lower bounds for dynamic connectivity. In: STOC, pp. 546\u2013553 (2004)","DOI":"10.1145\/1007352.1007435"},{"key":"21_CR16","doi-asserted-by":"crossref","unstructured":"Poutr\u00e9, J.A.L.: Alpha-algorithms for incremental planarity testing (preliminary version). In: STOC, pp. 706\u2013715 (1994)","DOI":"10.1145\/195058.195439"},{"key":"21_CR17","doi-asserted-by":"crossref","unstructured":"Protti, F., da Silva, M.D., Szwarcfiter, J.L.: Applying modular decomposition to parameterized cluster editing problems. Theory Comput. Syst. 44(1):91\u2013104 (2009)","DOI":"10.1007\/s00224-007-9032-7"},{"key":"21_CR18","unstructured":"Roditty, L.: A faster and simpler fully dynamic transitive closure. In: SODA, pp. 404\u2013412 (2003)"},{"key":"21_CR19","doi-asserted-by":"crossref","unstructured":"Roditty, L., Zwick, U.: Improved dynamic reachability algorithms for directed graphs. In: FOCS, pp. 679\u2013 (2002)","DOI":"10.1109\/SFCS.2002.1181993"},{"key":"21_CR20","doi-asserted-by":"crossref","unstructured":"Roditty, L., Zwick, U.: Dynamic approximate all-pairs shortest paths in undirected graphs. In: FOCS, pp. 499\u2013508 (2004)","DOI":"10.1109\/FOCS.2004.22"},{"key":"21_CR21","doi-asserted-by":"crossref","unstructured":"Roditty, L., Zwick, U.: A fully dynamic reachability algorithm for directed graphs with an almost linear update time. In: STOC, pp. 184\u2013191 (2004)","DOI":"10.1145\/1007352.1007387"},{"key":"21_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"580","DOI":"10.1007\/978-3-540-30140-0_52","volume-title":"Algorithms \u2013 ESA 2004","author":"L. Roditty","year":"2004","unstructured":"Roditty, L., Zwick, U.: On dynamic shortest paths problems. In: Albers, S., Radzik, T. (eds.) ESA 2004. LNCS, vol.\u00a03221, pp. 580\u2013591. Springer, Heidelberg (2004)"},{"key":"21_CR23","doi-asserted-by":"crossref","unstructured":"Sankowski, P.: Dynamic transitive closure via dynamic matrix inverse (extended abstract). In: FOCS, pp. 509\u2013517 (2004)","DOI":"10.1109\/FOCS.2004.25"},{"key":"21_CR24","doi-asserted-by":"crossref","unstructured":"Thorup, M.: Near-optimal fully-dynamic graph connectivity. In: STOC, pp. 343\u2013350 (2000)","DOI":"10.1145\/335305.335345"},{"key":"21_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"384","DOI":"10.1007\/978-3-540-27810-8_33","volume-title":"Algorithm Theory - SWAT 2004","author":"M. Thorup","year":"2004","unstructured":"Thorup, M.: Fully-dynamic all-pairs shortest paths: Faster and allowing negative cycles. In: Hagerup, T., Katajainen, J. (eds.) SWAT 2004. LNCS, vol.\u00a03111, pp. 384\u2013396. Springer, Heidelberg (2004)"},{"key":"21_CR26","doi-asserted-by":"crossref","unstructured":"Thorup, M.: Worst-case update times for fully-dynamic all-pairs shortest paths. In: STOC, pp. 112\u2013119 (2005)","DOI":"10.1145\/1060590.1060607"},{"key":"21_CR27","doi-asserted-by":"crossref","unstructured":"Wulff-Nilsen, C.: Faster deterministic fully-dynamic graph connectivity. In: SODA, pp. 1757\u20131769 (2013)","DOI":"10.1137\/1.9781611973105.126"}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory \u2013 SWAT 2014"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-08404-6_21","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,3]],"date-time":"2025-05-03T13:06:23Z","timestamp":1746277583000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-08404-6_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319084039","9783319084046"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-08404-6_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014]]}}}