{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T01:07:51Z","timestamp":1725757671696},"publisher-location":"Cham","reference-count":23,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319038971"},{"type":"electronic","value":"9783319038988"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-319-03898-8_24","type":"book-chapter","created":{"date-parts":[[2013,11,19]],"date-time":"2013-11-19T07:57:26Z","timestamp":1384847846000},"page":"281-294","source":"Crossref","is-referenced-by-count":31,"title":["On the Parameterized Complexity of Reconfiguration Problems"],"prefix":"10.1007","author":[{"given":"Amer E.","family":"Mouawad","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Naomi","family":"Nishimura","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Venkatesh","family":"Raman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Narges","family":"Simjour","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Akira","family":"Suzuki","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"doi-asserted-by":"crossref","unstructured":"Bonamy, M., Bousquet, N.: Recoloring bounded treewidth graphs. In: Proc. of Latin-American Algorithms Graphs and Optimization Symposium (2013)","key":"24_CR1","DOI":"10.1016\/j.endm.2013.10.040"},{"issue":"50","key":"24_CR2","doi-asserted-by":"publisher","first-page":"5215","DOI":"10.1016\/j.tcs.2009.08.023","volume":"410","author":"P.S. Bonsma","year":"2009","unstructured":"Bonsma, P.S., Cereceda, L.: Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances. Theor. Comput. Sci.\u00a0410(50), 5215\u20135226 (2009)","journal-title":"Theor. Comput. Sci."},{"issue":"56","key":"24_CR3","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. Discrete Mathematics\u00a0308(56), 913\u2013919 (2008)","journal-title":"Discrete Mathematics"},{"issue":"7","key":"24_CR4","doi-asserted-by":"publisher","first-page":"1593","DOI":"10.1016\/j.ejc.2009.03.011","volume":"30","author":"L. Cereceda","year":"2009","unstructured":"Cereceda, L., van den Heuvel, J., Johnson, M.: Mixing 3-colourings in bipartite graphs. European Journal of Combinatorics\u00a030(7), 1593\u20131606 (2009)","journal-title":"European Journal of Combinatorics"},{"issue":"1","key":"24_CR5","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\u00a067(1), 69\u201382 (2011)","journal-title":"Journal of Graph Theory"},{"issue":"15","key":"24_CR6","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\u00a0160(15), 2199\u20132207 (2012)","journal-title":"Discrete Applied Mathematics"},{"issue":"1-2","key":"24_CR7","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1016\/j.tcs.2005.05.008","volume":"343","author":"R.A. Hearn","year":"2005","unstructured":"Hearn, R.A., Demaine, E.D.: PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation. Theor. Comput. Sci.\u00a0343(1-2), 72\u201396 (2005)","journal-title":"Theor. Comput. Sci."},{"issue":"12-14","key":"24_CR8","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.\u00a0412(12-14), 1054\u20131065 (2011)","journal-title":"Theor. Comput. Sci."},{"issue":"6","key":"24_CR9","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.\u00a038(6), 2330\u20132355 (2009)","journal-title":"SIAM J. Comput."},{"key":"24_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"222","DOI":"10.1007\/978-3-642-32589-2_22","volume-title":"Mathematical Foundations of Computer Science 2012","author":"P. Bonsma","year":"2012","unstructured":"Bonsma, P.: The complexity of rerouting shortest paths. In: Rovan, B., Sassone, V., Widmayer, P. (eds.) MFCS 2012. LNCS, vol.\u00a07464, pp. 222\u2013233. Springer, Heidelberg (2012)"},{"issue":"39","key":"24_CR11","doi-asserted-by":"publisher","first-page":"5205","DOI":"10.1016\/j.tcs.2011.05.021","volume":"412","author":"M. Kami\u0144ski","year":"2011","unstructured":"Kami\u0144ski, M., Medvedev, P., Milani\u010d, M.: Shortest paths between shortest paths. Theor. Comput. Sci.\u00a0412(39), 5205\u20135210 (2011)","journal-title":"Theor. Comput. Sci."},{"unstructured":"Haas, R., Seyffarth, K.: The k-Dominating Graph, arXiv:1209.5138 (2012)","key":"24_CR12"},{"unstructured":"Suzuki, A., Mouawad, A.E., Nishimura, N.: Reconfiguration of dominating sets (submitted)","key":"24_CR13"},{"key":"24_CR14","volume-title":"Parameterized complexity","author":"R.G. Downey","year":"1997","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized complexity. Springer, New York (1997)"},{"key":"24_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"320","DOI":"10.1007\/978-3-540-70918-3_28","volume-title":"STACS 2007","author":"H.L. Bodlaender","year":"2007","unstructured":"Bodlaender, H.L.: A cubic kernel for feedback vertex set. In: Thomas, W., Weil, P. (eds.) STACS 2007. LNCS, vol.\u00a04393, pp. 320\u2013331. Springer, Heidelberg (2007)"},{"issue":"4","key":"24_CR16","doi-asserted-by":"publisher","first-page":"391","DOI":"10.1016\/j.jda.2009.01.003","volume":"7","author":"P. Damaschke","year":"2009","unstructured":"Damaschke, P., Molokov, L.: The union of minimal hitting sets: Parameterized combinatorial bounds and counting. Journal of Discrete Algorithms\u00a07(4), 391\u2013401 (2009)","journal-title":"Journal of Discrete Algorithms"},{"key":"24_CR17","volume-title":"Parameterized complexity theory","author":"J. Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized complexity theory. Springer, Berlin (2006)"},{"doi-asserted-by":"crossref","unstructured":"Niedermeier, R.: Invitation to fixed-parameter algorithms. Oxford University Press (2006)","key":"24_CR18","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001"},{"issue":"2","key":"24_CR19","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1016\/0022-0000(80)90060-4","volume":"20","author":"J.M. Lewis","year":"1980","unstructured":"Lewis, J.M., Yannakakis, M.: The node-deletion problem for hereditary properties is NP-complete. Journal of Computer and System Sciences\u00a020(2), 219\u2013230 (1980)","journal-title":"Journal of Computer and System Sciences"},{"doi-asserted-by":"crossref","unstructured":"Mouawad, A.E., Nishimura, N., Raman, V., Simjour, N., Suzuki, A.: On the parameterized complexity of reconfiguration problems, arXiv:1308.2409 (2013)","key":"24_CR20","DOI":"10.1007\/978-3-319-03898-8_24"},{"issue":"8","key":"24_CR21","doi-asserted-by":"publisher","first-page":"1386","DOI":"10.1016\/j.jcss.2006.02.001","volume":"72","author":"J. Guo","year":"2006","unstructured":"Guo, J., Gramm, J., H\u00fcffner, F., Niedermeier, R., Wernicke, S.: Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization. Journal of Computer and System Sciences\u00a072(8), 1386\u20131396 (2006)","journal-title":"Journal of Computer and System Sciences"},{"issue":"2","key":"24_CR22","doi-asserted-by":"publisher","first-page":"997","DOI":"10.1016\/S0304-3975(01)00414-5","volume":"289","author":"S. Khot","year":"2002","unstructured":"Khot, S., Raman, V.: Parameterized complexity of finding subgraphs with hereditary properties. Theor. Comput. Sci.\u00a0289(2), 997\u20131008 (2002)","journal-title":"Theor. Comput. Sci."},{"unstructured":"Fellows, M.R., Rosamond, F.A., Fomin, F.V., Lokshtanov, D., Saurabh, S., Villanger, Y.: Local search: is brute-force avoidable? In: Proc. of the 21st International Joint Conference on Artifical Intelligence, pp. 486\u2013491 (2009)","key":"24_CR23"}],"container-title":["Lecture Notes in Computer Science","Parameterized and Exact Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-03898-8_24","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T10:46:24Z","timestamp":1558694784000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-03898-8_24"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783319038971","9783319038988"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-03898-8_24","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}