{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T02:53:48Z","timestamp":1743130428761,"version":"3.40.3"},"publisher-location":"Cham","reference-count":28,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319218397"},{"type":"electronic","value":"9783319218403"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"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":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-21840-3_42","type":"book-chapter","created":{"date-parts":[[2015,7,27]],"date-time":"2015-07-27T09:57:38Z","timestamp":1437991058000},"page":"506-517","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Reconfiguration on Sparse Graphs"],"prefix":"10.1007","author":[{"given":"Daniel","family":"Lokshtanov","sequence":"first","affiliation":[]},{"given":"Amer E.","family":"Mouawad","sequence":"additional","affiliation":[]},{"given":"Fahad","family":"Panolan","sequence":"additional","affiliation":[]},{"given":"M. S.","family":"Ramanujan","sequence":"additional","affiliation":[]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,7,28]]},"reference":[{"issue":"4","key":"42_CR1","doi-asserted-by":"publisher","first-page":"544","DOI":"10.1007\/s00453-008-9204-0","volume":"54","author":"N Alon","year":"2009","unstructured":"Alon, N., Gutner, S.: Linear time algorithms for finding a dominating set of fixed size in degenerated graphs. Algorithmica 54(4), 544\u2013556 (2009)","journal-title":"Algorithmica"},{"key":"42_CR2","unstructured":"Bonsma, P.: Rerouting shortest paths in planar graphs. In: Proceedings of the 32nd Annual Conference on Foundations of Software Technology and Theoretical Computer Science, pp. 337\u2013349 (2012)"},{"issue":"1","key":"42_CR3","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1016\/j.comgeo.2008.04.001","volume":"42","author":"P Bose","year":"2009","unstructured":"Bose, P., Hurtado, F.: Flips in planar graphs. Computational Geometry 42(1), 60\u201380 (2009)","journal-title":"Computational Geometry"},{"issue":"1","key":"42_CR4","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1002\/jgt.20514","volume":"67","author":"L Cereceda","year":"2011","unstructured":"Cereceda, L., van den Heuvel, J., Johnson, M.: Finding paths between 3-colorings. Journal of Graph Theory 67(1), 69\u201382 (2011)","journal-title":"Journal of Graph Theory"},{"issue":"16","key":"42_CR5","doi-asserted-by":"publisher","first-page":"918","DOI":"10.1016\/j.ipl.2009.04.023","volume":"109","author":"S Cleary","year":"2009","unstructured":"Cleary, S., John, K.S.: Rotation distance is fixed-parameter tractable. Information Processing Letters 109(16), 918\u2013922 (2009)","journal-title":"Information Processing Letters"},{"issue":"5","key":"42_CR6","doi-asserted-by":"publisher","first-page":"324","DOI":"10.1016\/j.jcss.2009.10.005","volume":"76","author":"A Dawar","year":"2010","unstructured":"Dawar, A.: Homomorphism preservation on quasi-wide classes. Journal of Computer and System Sciences 76(5), 324\u2013332 (2010). Workshop on Logic, Language, Information and Computation","journal-title":"Journal of Computer and System Sciences"},{"key":"42_CR7","unstructured":"Dawar, A., Kreutzer, S.: Domination problems in nowhere-dense classes of graphs. CoRR (2009). arXiv:0907.42837"},{"key":"42_CR8","doi-asserted-by":"crossref","unstructured":"Diestel, R.: Graph theory, Electronic Edition. Springer (2005)","DOI":"10.1007\/978-3-642-14279-6_7"},{"key":"42_CR9","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized complexity. Springer, New York (1997)"},{"key":"42_CR10","unstructured":"Drange, P.G., Dregi, M.S., Fomin, F.V., Kreutzer, S., Lokshtanov, D., Pilipczuk, M., Pilipczuk, M., Reidl, F., Saurabh, S., Villaamil, F.S., Sikdar, S.: Kernelization and sparseness: the case of dominating set. CoRR (2014). arXiv:1411.4575"},{"key":"42_CR11","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1112\/jlms\/s1-35.1.85","volume":"35","author":"P Erd\u0151s","year":"1960","unstructured":"Erd\u0151s, P., Rado, R.: Intersection theorems for systems of sets. Journal of the London Mathematical Society 35, 85\u201390 (1960)","journal-title":"Journal of the London Mathematical Society"},{"issue":"6","key":"42_CR12","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 Journal on Computing 38(6), 2330\u20132355 (2009)","journal-title":"SIAM Journal on Computing"},{"key":"42_CR13","unstructured":"Grohe, M., Kreutzer, S., Siebertz, S.: Characterisations of nowhere dense graphs. In: Proceedings of the 33rd Annual Conference on Foundations of Software Technology and Theoretical Computer Science, pp. 21\u201340 (2013)"},{"key":"42_CR14","doi-asserted-by":"crossref","unstructured":"Grohe, M., Kreutzer, S., Siebertz, S.: Deciding first-order properties of nowhere dense graphs. In: Proceedings of the 46th Annual ACM Symposium on Theory of Computing, pp. 89\u201398 (2014)","DOI":"10.1145\/2591796.2591851"},{"issue":"12\u201314","key":"42_CR15","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. Theoretical Computer Science 412(12\u201314), 1054\u20131065 (2011)","journal-title":"Theoretical Computer Science"},{"issue":"15","key":"42_CR16","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. Discrete Applied Mathematics 160(15), 2199\u20132207 (2012)","journal-title":"Discrete Applied Mathematics"},{"key":"42_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"208","DOI":"10.1007\/978-3-319-13075-0_17","volume-title":"Algorithms and Computation","author":"T Ito","year":"2014","unstructured":"Ito, T., Kami\u0144ski, M., Ono, H.: Fixed-parameter tractability of token jumping on planar graphs. In: Ahn, H.-K., Shin, C.-S. (eds.) ISAAC 2014. LNCS, vol. 8889, pp. 208\u2013219. Springer, Heidelberg (2014)"},{"key":"42_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1007\/978-3-319-06089-7_24","volume-title":"Theory and Applications of Models of Computation","author":"T Ito","year":"2014","unstructured":"Ito, T., Kami\u0144ski, M., Ono, H., Suzuki, A., Uehara, R., Yamanaka, K.: On the parameterized complexity for token jumping on graphs. In: Gopal, T.V., Agrawal, M., Li, A., Cooper, S.B. (eds.) TAMC 2014. LNCS, vol. 8402, pp. 341\u2013351. Springer, Heidelberg (2014)"},{"key":"42_CR19","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1016\/j.tcs.2012.03.004","volume":"439","author":"M Kami\u0144ski","year":"2012","unstructured":"Kami\u0144ski, M., Medvedev, P., Milani\u010d, M.: Complexity of independent set reconfigurability problems. Theoretical Computer Science 439, 9\u201315 (2012)","journal-title":"Theoretical Computer Science"},{"key":"42_CR20","unstructured":"Lubiw, A., Pathak, V.: Flip distance between two triangulations of a point-set is NP-complete. CoRR (2012). arXiv:1205.2425"},{"key":"42_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1007\/978-3-319-03898-8_24","volume-title":"Parameterized and Exact Computation","author":"AE Mouawad","year":"2013","unstructured":"Mouawad, A.E., Nishimura, N., Raman, V., Simjour, N., Suzuki, A.: On the parameterized complexity of reconfiguration problems. In: Gutin, G., Szeider, S. (eds.) IPEC 2013. LNCS, vol. 8246, pp. 281\u2013294. Springer, Heidelberg (2013)"},{"key":"42_CR22","doi-asserted-by":"crossref","unstructured":"Nesetril, J., de Mendez, P.O.: Structural properties of sparse graphs. In: Building Bridges. Bolyai Society Mathematical Studies, vol. 19, pp. 369\u2013426. Springer, Heidelberg (2008)","DOI":"10.1007\/978-3-540-85221-6_13"},{"issue":"3","key":"42_CR23","doi-asserted-by":"publisher","first-page":"868","DOI":"10.2178\/jsl\/1278682204","volume":"75","author":"J Nesetril","year":"2010","unstructured":"Nesetril, J., de Mendez, P.O.: First order properties on nowhere dense structures. Journal of Symbolic Logic 75(3), 868\u2013887 (2010)","journal-title":"Journal of Symbolic Logic"},{"key":"42_CR24","unstructured":"Nesetril, J., de Mendez, P.O.: From sparse graphs to nowhere dense structures: Decompositions, independence, dualities and limits. European Congress of Mathematics (2010)"},{"key":"42_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"694","DOI":"10.1007\/978-3-642-04128-0_62","volume-title":"Algorithms - ESA 2009","author":"G Philip","year":"2009","unstructured":"Philip, G., Raman, V., Sikdar, S.: Solving dominating set in larger classes of graphs: FPT algorithms and polynomial kernels. In: Fiat, A., Sanders, P. (eds.) ESA 2009. LNCS, vol. 5757, pp. 694\u2013705. Springer, Heidelberg (2009)"},{"key":"42_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"802","DOI":"10.1007\/978-3-642-33090-2_69","volume-title":"Algorithms \u2013 ESA 2012","author":"JA Telle","year":"2012","unstructured":"Telle, J.A., Villanger, Y.: FPT algorithms for domination in biclique-free graphs. In: Epstein, L., Ferragina, P. (eds.) ESA 2012. LNCS, vol. 7501, pp. 802\u2013812. Springer, Heidelberg (2012)"},{"issue":"409","key":"42_CR27","first-page":"127","volume":"2013","author":"J van den Heuvel","year":"2013","unstructured":"van den Heuvel, J.: The complexity of change. Surveys in Combinatorics 2013(409), 127\u2013160 (2013)","journal-title":"Surveys in Combinatorics"},{"key":"42_CR28","unstructured":"Wrochna, M.: Reconfiguration in bounded bandwidth and treedepth. CoRR (2014). arXiv:1405.0847"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-21840-3_42","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,21]],"date-time":"2023-02-21T05:47:19Z","timestamp":1676958439000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-21840-3_42"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319218397","9783319218403"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-21840-3_42","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"28 July 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}