{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,15]],"date-time":"2026-04-15T20:26:05Z","timestamp":1776284765660,"version":"3.50.1"},"publisher-location":"Cham","reference-count":23,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319171418","type":"print"},{"value":"9783319171425","type":"electronic"}],"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-17142-5_19","type":"book-chapter","created":{"date-parts":[[2015,4,15]],"date-time":"2015-04-15T11:19:29Z","timestamp":1429096769000},"page":"212-223","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":17,"title":["Reconfiguration of Cliques in a Graph"],"prefix":"10.1007","author":[{"given":"Takehiro","family":"Ito","sequence":"first","affiliation":[]},{"given":"Hirotaka","family":"Ono","sequence":"additional","affiliation":[]},{"given":"Yota","family":"Otachi","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,4,16]]},"reference":[{"key":"19_CR1","doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L., Drange, P.G., Dregi, M.S., Fomin, F.V., Lokshtanov, D., Pilipczuk, M.: An $$O(c^k n)$$\n                    $$5$$-approximation algorithm for treewidth. In: Proceedings of FOCS 2013, pp. 499\u2013508 (2013)","DOI":"10.1109\/FOCS.2013.60"},{"key":"19_CR2","doi-asserted-by":"publisher","first-page":"5215","DOI":"10.1016\/j.tcs.2009.08.023","volume":"410","author":"P Bonsma","year":"2009","unstructured":"Bonsma, P., Cereceda, L.: Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances. Theoret. Comput. Sci. 410, 5215\u20135226 (2009)","journal-title":"Theoret. Comput. Sci."},{"key":"19_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/978-3-319-12340-0_9","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"P Bonsma","year":"2014","unstructured":"Bonsma, P.: Independent set reconfiguration in cographs. In: Kratsch, D., Todinca, I. (eds.) WG 2014. LNCS, vol. 8747, pp. 105\u2013116. Springer, Heidelberg (2014)"},{"key":"19_CR4","doi-asserted-by":"crossref","unstructured":"Brandst\u00e4dt, A., Le, V.B., Spinrad, J.P.: Graph Classes: A Survey, SIAM, Philadelphia (1999)","DOI":"10.1137\/1.9780898719796"},{"key":"19_CR5","doi-asserted-by":"publisher","first-page":"1065","DOI":"10.1016\/j.disc.2006.07.027","volume":"307","author":"MVG da Silva","year":"2007","unstructured":"da Silva, M.V.G., Vu\u0161kovi\u0107, K.: Triangulated neighborhoods in even-hole-free graphs. Discrete Math. 307, 1065\u20131073 (2007)","journal-title":"Discrete Math."},{"key":"19_CR6","doi-asserted-by":"publisher","first-page":"835","DOI":"10.2140\/pjm.1965.15.835","volume":"15","author":"DR Fulkerson","year":"1965","unstructured":"Fulkerson, D.R., Gross, O.A.: Incidence matrices and interval graphs. Pac. J. Math. 15, 835\u2013855 (1965)","journal-title":"Pac. J. Math."},{"key":"19_CR7","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco (1979)"},{"key":"19_CR8","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/0095-8956(74)90094-X","volume":"16","author":"F Gavril","year":"1974","unstructured":"Gavril, F.: The intersection graphs of subtrees in trees are exactly the chordal graphs. J. Comb. Theory, Ser. B 16, 47\u201356 (1974)","journal-title":"J. Comb. Theory, Ser. B"},{"key":"19_CR9","doi-asserted-by":"publisher","first-page":"539","DOI":"10.4153\/CJM-1964-055-5","volume":"16","author":"PC Gilmore","year":"1964","unstructured":"Gilmore, P.C., Hoffman, A.J.: A characterization of comparability graphs and of interval graphs. Can. J. Math. 16, 539\u2013548 (1964)","journal-title":"Can. J. Math."},{"key":"19_CR10","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, 2330\u20132355 (2009)","journal-title":"SIAM J. Comput."},{"key":"19_CR11","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1016\/j.tcs.2005.05.008","volume":"343","author":"RA 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. Theoret. Comput. Sci. 343, 72\u201396 (2005)","journal-title":"Theoret. Comput. Sci."},{"key":"19_CR12","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. Theoret. Comput. Sci. 412, 1054\u20131065 (2011)","journal-title":"Theoret. Comput. Sci."},{"key":"19_CR13","doi-asserted-by":"crossref","unstructured":"Ito, T., Nooka, H., Zhou, X.: Reconfiguration of vertex covers in a graph. In: Proceedings of IWOCA 2014 (2014, To appear)","DOI":"10.1007\/978-3-319-19315-1_15"},{"key":"19_CR14","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. Theoret. Comput. Sci. 439, 9\u201315 (2012)","journal-title":"Theoret. Comput. Sci."},{"key":"19_CR15","doi-asserted-by":"crossref","unstructured":"Lee, C., Oum, S.: Number of cliques in graphs with forbidden subdivision. arXiv:1407.7707 (2014)","DOI":"10.1137\/140979988"},{"key":"19_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"447","DOI":"10.1007\/978-3-319-13075-0_36","volume-title":"Algorithms and Computation","author":"AE Mouawad","year":"2014","unstructured":"Mouawad, A.E., Nishimura, N., Raman, V.: Vertex cover reconfiguration and beyond. In: Ahn, H.-K., Shin, C.-S. (eds.) ISAAC 2014. LNCS, vol. 8889, pp. 447\u2013458. Springer, Heidelberg (2014)"},{"key":"19_CR17","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":"19_CR18","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","volume":"7","author":"N Robertson","year":"1986","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. II. Algorithmic aspects of tree-width. J. Algorithms 7, 309\u2013322 (1986)","journal-title":"J. Algorithms"},{"key":"19_CR19","volume-title":"Efficient Graph Representations","author":"JP Spinrad","year":"2003","unstructured":"Spinrad, J.P.: Efficient Graph Representations. American Mathematical Society, Providence (2003)"},{"key":"19_CR20","doi-asserted-by":"publisher","first-page":"505","DOI":"10.1137\/0206036","volume":"6","author":"S Tsukiyama","year":"1977","unstructured":"Tsukiyama, S., Ide, M., Ariyoshi, H., Shirakawa, I.: A new algorithm for generating all the maximal independent sets. SIAM J. Comput. 6, 505\u2013517 (1977)","journal-title":"SIAM J. Comput."},{"key":"19_CR21","doi-asserted-by":"publisher","first-page":"911","DOI":"10.1142\/S0129054107005054","volume":"18","author":"R Uehara","year":"2007","unstructured":"Uehara, R., Uno, Y.: On computing longest paths in small graph classes. Int. J. Found. Comput. Sci. 18, 911\u2013930 (2007)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"19_CR22","doi-asserted-by":"crossref","unstructured":"van den Heuvel, J.: The complexity of change. Surveys in Combinatorics 2013, London Mathematical Society Lecture Notes Series 409 (2013)","DOI":"10.1017\/CBO9781139506748.005"},{"key":"19_CR23","unstructured":"Wrochna, M.: Reconfiguration in bounded bandwidth and treedepth. arXiv:1405.0847 (2014)"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Models of Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-17142-5_19","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,21]],"date-time":"2023-02-21T00:37:29Z","timestamp":1676939849000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-17142-5_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319171418","9783319171425"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-17142-5_19","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"16 April 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}