{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,5]],"date-time":"2026-03-05T13:32:07Z","timestamp":1772717527595,"version":"3.50.1"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2022,1,14]],"date-time":"2022-01-14T00:00:00Z","timestamp":1642118400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,1,14]],"date-time":"2022-01-14T00:00:00Z","timestamp":1642118400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2022,2]]},"DOI":"10.1007\/s00453-021-00909-5","type":"journal-article","created":{"date-parts":[[2022,1,14]],"date-time":"2022-01-14T00:03:06Z","timestamp":1642118586000},"page":"482-509","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["On the Parameterized Complexity of Reconfiguration of Connected Dominating Sets"],"prefix":"10.1007","volume":"84","author":[{"given":"Daniel","family":"Lokshtanov","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2481-4968","authenticated-orcid":false,"given":"Amer E.","family":"Mouawad","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fahad","family":"Panolan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sebastian","family":"Siebertz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,1,14]]},"reference":[{"key":"909_CR1","doi-asserted-by":"publisher","unstructured":"Blum, J., Ding, M., Thaeler, A., Cheng, X.: Connected dominating set in sensor networks and MANETs, pp. 329\u2013369 (2006). https:\/\/doi.org\/10.1007\/0-387-23830-1_8","DOI":"10.1007\/0-387-23830-1_8"},{"issue":"56","key":"909_CR2","doi-asserted-by":"publisher","first-page":"913","DOI":"10.1016\/j.disc.2007.07.028","volume":"308","author":"L Cereceda","year":"2008","unstructured":"Cereceda, L., van den Heuvel, J., Johnson, M.: Connectedness of the graph of vertex-colourings. Discr. Math. 308(56), 913\u2013919 (2008)","journal-title":"Discr. Math."},{"issue":"2","key":"909_CR3","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/s002249910009","volume":"33","author":"B Courcelle","year":"2000","unstructured":"Courcelle, B., Makowsky, J.A., Rotics, U.: Linear time solvable optimization problems on graphs of bounded clique-width. Theory Comput. Syst. 33(2), 125\u2013150 (2000)","journal-title":"Theory Comput. Syst."},{"key":"909_CR4","doi-asserted-by":"publisher","unstructured":"Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Berlin (2015). https:\/\/doi.org\/10.1007\/978-3-319-21275-3","DOI":"10.1007\/978-3-319-21275-3"},{"key":"909_CR5","unstructured":"Dawar, A., Kreutzer, S.: Domination problems in nowhere-dense classes. In: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2009, pp. 157\u2013168 (2009)"},{"key":"909_CR6","doi-asserted-by":"crossref","unstructured":"Demaine, E.D., O\u2019Rourke, J.: Geometric Folding Algorithms\u2014Linkages, Origami, Polyhedra. Cambridge University Press, Cambrige (2007)","DOI":"10.1017\/CBO9780511735172"},{"key":"909_CR7","unstructured":"Drange, P.G., Dregi, M.S., Fomin, F.V., Kreutzer, S., Lokshtanov, D., Pilipczuk, M., Pilipczuk, M., Reidl, F., Villaamil, F.S., Saurabh, S., Siebertz, S., Sikdar, S.: Kernelization and sparseness: the case of dominating set. In: 33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016, pp. 31:1\u201331:14 (2016)"},{"key":"909_CR8","unstructured":"Eiben, E., Kumar, M., Mouawad, A.E., Panolan, F., Siebertz, S.: Lossy kernels for connected dominating set on sparse graphs. In: 35th Symposium on Theoretical Aspects of Computer Science, STACS 2018, pp. 29:1\u201329:15 (2018)"},{"key":"909_CR9","unstructured":"Eickmeyer, K., Giannopoulou, A.C., Kreutzer, S., Kwon, O., Pilipczuk, M., Rabinovich, R., Siebertz, S.: Neighborhood complexity and kernelization for nowhere dense classes of graphs. In: 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, pp. 63:1\u201363:14 (2017)"},{"key":"909_CR10","unstructured":"Fabianski, G., Pilipczuk, M., Siebertz, S., Toru\u0144czyk, S.: Progressive algorithms for domination and independence. In: 36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019, pp. 27:1\u201327:16 (2019)"},{"key":"909_CR11","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1016\/j.jcss.2016.09.002","volume":"84","author":"J Gajarsk\u00fd","year":"2017","unstructured":"Gajarsk\u00fd, J., Hlinen\u00fd, P., Obdrz\u00e1lek, J., Ordyniak, S., Reidl, F., Rossmanith, P., Villaamil, F.S., Sikdar, S.: Kernelization using structural parameters on sparse graph classes. J. Comput. Syst. Sci. 84, 219\u2013242 (2017)","journal-title":"J. Comput. Syst. Sci."},{"key":"909_CR12","doi-asserted-by":"crossref","unstructured":"Gharibian, S., Sikora, J.: Ground state connectivity of local hamiltonians. In: Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming, ICALP 2015, pp. 617\u2013628 (2015)","DOI":"10.1007\/978-3-662-47672-7_50"},{"issue":"6","key":"909_CR13","doi-asserted-by":"publisher","first-page":"2330","DOI":"10.1137\/07070440X","volume":"38","author":"P Gopalan","year":"2009","unstructured":"Gopalan, P., Kolaitis, P.G., Maneva, E.N., Papadimitriou, C.H.: The connectivity of Boolean satisfiability: computational and structural dichotomies. SIAM J. Comput. 38(6), 2330\u20132355 (2009)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"909_CR14","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1145\/3051095","volume":"64","author":"M Grohe","year":"2017","unstructured":"Grohe, M., Kreutzer, S., Siebertz, S.: Deciding first-order properties of nowhere dense graphs. J. ACM (JACM) 64(3), 17 (2017)","journal-title":"J. ACM (JACM)"},{"key":"909_CR15","doi-asserted-by":"publisher","unstructured":"Gupta, A., Kumar, A., Roughgarden, T.: Simpler and better approximation algorithms for network design. In: L.L. Larmore, M.X. Goemans (eds.) Proceedings of the 35th Annual ACM Symposium on Theory of Computing, June 9\u201311, 2003, San Diego, CA, USA, pp. 365\u2013372. ACM (2003). https:\/\/doi.org\/10.1145\/780542.780597","DOI":"10.1145\/780542.780597"},{"issue":"3","key":"909_CR16","doi-asserted-by":"publisher","first-page":"609","DOI":"10.1007\/s00373-013-1302-3","volume":"30","author":"R Haas","year":"2014","unstructured":"Haas, R., Seyffarth, K.: The k-dominating graph. Graphs Comb. 30(3), 609\u2013617 (2014)","journal-title":"Graphs Comb."},{"key":"909_CR17","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/j.tcs.2016.08.016","volume":"651","author":"A Haddadan","year":"2016","unstructured":"Haddadan, A., Ito, T., Mouawad, A.E., Nishimura, N., Ono, H., Suzuki, A., Tebbal, Y.: The complexity of dominating set reconfiguration. Theor. Comput. Sci. 651, 37\u201349 (2016). https:\/\/doi.org\/10.1016\/j.tcs.2016.08.016","journal-title":"Theor. Comput. Sci."},{"issue":"2013","key":"909_CR18","first-page":"127","volume":"409","author":"J van den Heuvel","year":"2013","unstructured":"van den Heuvel, J.: The complexity of change. Surv. Comb. 409(2013), 127\u2013160 (2013)","journal-title":"Surv. Comb."},{"issue":"12\u201314","key":"909_CR19","doi-asserted-by":"publisher","first-page":"1054","DOI":"10.1016\/j.tcs.2010.12.005","volume":"412","author":"T Ito","year":"2011","unstructured":"Ito, T., Demaine, E.D., Harvey, N.J.A., Papadimitriou, C.H., Sideri, M., Uehara, R., Uno, Y.: On the complexity of reconfiguration problems. Theor. Comput. Sci. 412(12\u201314), 1054\u20131065 (2011)","journal-title":"Theor. Comput. Sci."},{"issue":"15","key":"909_CR20","doi-asserted-by":"publisher","first-page":"2199","DOI":"10.1016\/j.dam.2012.05.014","volume":"160","author":"T Ito","year":"2012","unstructured":"Ito, T., Kami\u0144ski, M., Demaine, E.D.: Reconfiguration of list edge-colorings in a graph. Discr. Appl. Math. 160(15), 2199\u20132207 (2012)","journal-title":"Discr. Appl. Math."},{"key":"909_CR21","doi-asserted-by":"crossref","unstructured":"Johnson, W.W., Story, W.E.: Notes on the \u201c15\u201d puzzle. Am. J. Math. 2(4), 397\u2013404 (1879)","DOI":"10.2307\/2369492"},{"key":"909_CR22","unstructured":"Kanj, I.A., Xia, G.: Flip distance is in FPT time o(n+ k * c$${\\hat{\\,}}$$k). In: 32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015, pp. 500\u2013512 (2015)"},{"key":"909_CR23","doi-asserted-by":"crossref","unstructured":"Kendall, G., Parkes, A.J., Spoerer, K.: A survey of NP-complete puzzles. ICGA J., pp. 13\u201334 (2008)","DOI":"10.3233\/ICG-2008-31103"},{"key":"909_CR24","doi-asserted-by":"crossref","unstructured":"Kreutzer, S., Rabinovich, R., Siebertz, S.: Polynomial kernels and wideness properties of nowhere dense graph classes. In: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, pp. 1533\u20131545 (2017)","DOI":"10.1137\/1.9781611974782.100"},{"key":"909_CR25","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1016\/j.jcss.2018.02.004","volume":"95","author":"D Lokshtanov","year":"2018","unstructured":"Lokshtanov, D., Mouawad, A.E., Panolan, F., Ramanujan, M.S., Saurabh, S.: Reconfiguration on sparse graphs. J. Comput. Syst. Sci. 95, 122\u2013131 (2018)","journal-title":"J. Comput. Syst. Sci."},{"key":"909_CR26","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1016\/j.comgeo.2014.11.001","volume":"49","author":"A Lubiw","year":"2015","unstructured":"Lubiw, A., Pathak, V.: Flip distance between two triangulations of a point set is NP-complete. Comput. Geom. 49, 17\u201323 (2015)","journal-title":"Comput. Geom."},{"key":"909_CR27","unstructured":"Mouawad, A.E.: On reconfiguration problems: structure and tractability (2015)"},{"key":"909_CR28","doi-asserted-by":"crossref","unstructured":"Mouawad, A.E., Nishimura, N., Pathak, V., Raman, V.: Shortest reconfiguration paths in the solution space of Boolean formulas. In: Automata, Languages, and Programming\u201442nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6\u201310, 2015, Proceedings, Part I, pp. 985\u2013996 (2015)","DOI":"10.1007\/978-3-662-47672-7_80"},{"issue":"1","key":"909_CR29","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1007\/s00453-016-0159-2","volume":"78","author":"AE Mouawad","year":"2017","unstructured":"Mouawad, A.E., Nishimura, N., Raman, V., Simjour, N., Suzuki, A.: On the parameterized complexity of reconfiguration problems. Algorithmica 78(1), 274\u2013297 (2017)","journal-title":"Algorithmica"},{"key":"909_CR30","doi-asserted-by":"crossref","unstructured":"Nadara, W., Pilipczuk, M., Rabinovich, R., Reidl, F., Siebertz, S.: Empirical evaluation of approximation algorithms for generalized graph coloring and uniform quasi-wideness. In: 17th International Symposium on Experimental Algorithms, SEA 2018, pp. 14:1\u201314:16 (2018)","DOI":"10.1145\/3368630"},{"key":"909_CR31","doi-asserted-by":"crossref","unstructured":"Nishimura, N.: Introduction to reconfiguration. Algorithms 11(4), 52 (2018)","DOI":"10.3390\/a11040052"},{"key":"909_CR32","doi-asserted-by":"crossref","unstructured":"Pilipczuk, M., Siebertz, S., Toru\u0144czyk, S.: On the number of types in sparse graphs. In: Proceedings of the 33rd Annual ACM\/IEEE Symposium on Logic in Computer Science, pp. 799\u2013808. ACM (2018)","DOI":"10.1145\/3209108.3209178"},{"key":"909_CR33","doi-asserted-by":"crossref","unstructured":"Siebertz, S.: Reconfiguration on nowhere dense graph classes. Electr. J. Comb. 25(3), P3.24 (2018)","DOI":"10.37236\/7458"},{"issue":"4","key":"909_CR34","doi-asserted-by":"publisher","first-page":"1182","DOI":"10.1007\/s10878-015-9947-x","volume":"32","author":"A Suzuki","year":"2016","unstructured":"Suzuki, A., Mouawad, A.E., Nishimura, N.: Reconfiguration of dominating sets. J. Comb. Optim. 32(4), 1182\u20131195 (2016)","journal-title":"J. Comb. Optim."},{"key":"909_CR35","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1007\/3-540-45753-4_22","volume-title":"Approximation Algorithms for Combinatorial Optimization","author":"C Swamy","year":"2002","unstructured":"Swamy, C., Kumar, A.: Primal-dual algorithms for connected facility location problems. In: Jansen, K., Leonardi, S., Vazirani, V. (eds.) Approximation Algorithms for Combinatorial Optimization, pp. 256\u2013270. Springer, Berlin (2002)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00909-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-021-00909-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00909-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,2,15]],"date-time":"2022-02-15T07:04:39Z","timestamp":1644908679000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-021-00909-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,14]]},"references-count":35,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,2]]}},"alternative-id":["909"],"URL":"https:\/\/doi.org\/10.1007\/s00453-021-00909-5","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,1,14]]},"assertion":[{"value":"28 September 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 November 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 January 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}