{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,7,30]],"date-time":"2024-07-30T01:32:36Z","timestamp":1722303156728},"reference-count":16,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2012,4,26]],"date-time":"2012-04-26T00:00:00Z","timestamp":1335398400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2014,1]]},"DOI":"10.1007\/s10878-012-9490-y","type":"journal-article","created":{"date-parts":[[2012,4,25]],"date-time":"2012-04-25T18:37:59Z","timestamp":1335379079000},"page":"132-143","source":"Crossref","is-referenced-by-count":55,"title":["Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs"],"prefix":"10.1007","volume":"27","author":[{"given":"Marthe","family":"Bonamy","sequence":"first","affiliation":[]},{"given":"Matthew","family":"Johnson","sequence":"additional","affiliation":[]},{"given":"Ioannis","family":"Lignos","sequence":"additional","affiliation":[]},{"given":"Viresh","family":"Patel","sequence":"additional","affiliation":[]},{"given":"Dani\u00ebl","family":"Paulusma","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2012,4,26]]},"reference":[{"key":"9490_CR1","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1002\/rsa.20323","volume":"38","author":"D Achlioptas","year":"2011","unstructured":"Achlioptas D, Coja-Oghlan A, Ricci-Tersenghi F (2011) On the solution-space geometry of random constraint satisfaction problems. Random Struct Algorithms 38:251\u2013268","journal-title":"Random Struct Algorithms"},{"key":"9490_CR2","unstructured":"Bonsma P (2010) Shortest path reconfiguration is PSPACE-hard. Manuscript. arXiv: 1009.3217"},{"key":"9490_CR3","doi-asserted-by":"crossref","first-page":"5215","DOI":"10.1016\/j.tcs.2009.08.023","volume":"410","author":"P Bonsma","year":"2009","unstructured":"Bonsma P, Cereceda L (2009) Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances. Theor Comput Sci 410:5215\u20135226","journal-title":"Theor Comput Sci"},{"key":"9490_CR4","unstructured":"Cereceda L (2007) Mixing graph colourings. PhD thesis, London School of Economics and Political Science"},{"key":"9490_CR5","doi-asserted-by":"crossref","first-page":"1593","DOI":"10.1016\/j.ejc.2009.03.011","volume":"30","author":"L Cereceda","year":"2009","unstructured":"Cereceda L, van\u00a0den Heuvel J, Johnson M (2009) Mixing 3-colourings in bipartite graphs. Eur J Comb 30:1593\u20131606","journal-title":"Eur J Comb"},{"key":"9490_CR6","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1002\/jgt.20514","volume":"67","author":"L Cereceda","year":"2011","unstructured":"Cereceda L, van\u00a0den Heuvel J, Johnson M (2011) Finding paths between 3-colourings. J Graph Theory 67:69\u201382","journal-title":"J Graph Theory"},{"key":"9490_CR7","doi-asserted-by":"crossref","unstructured":"Diestel R (2005) Graph theory. Springer-Verlag, Electronic edition","DOI":"10.4171\/owr\/2005\/03"},{"key":"9490_CR8","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1007\/BF02992776","volume":"25","author":"GA Dirac","year":"1961","unstructured":"Dirac GA (1961) On rigid circuit graphs. Anh Math Semin Univ Hamburg 25:71\u201376","journal-title":"Anh Math Semin Univ Hamburg"},{"key":"9490_CR9","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1016\/0095-8956(74)90094-X","volume":"16","author":"F Gavril","year":"1974","unstructured":"Gavril F (1974) The intersection graphs of subtrees in trees are exactly the chordal graphs. J Comb Theory, Ser B 16:47\u201356","journal-title":"J Comb Theory, Ser B"},{"key":"9490_CR10","series-title":"Annals of discrete mathematics","volume-title":"Algorithmic graph theory and perfect graphs","author":"MC Golumbic","year":"2004","unstructured":"Golumbic MC (2004) Algorithmic graph theory and perfect graphs. Annals of discrete mathematics, vol 57. Elsevier, Amsterdam"},{"key":"9490_CR11","doi-asserted-by":"crossref","first-page":"2330","DOI":"10.1137\/07070440X","volume":"38","author":"P Gopalan","year":"2009","unstructured":"Gopalan P, Kolaitis PG, Maneva EN, Papadimitriou CH (2009) The connectivity of boolean satisfiability: computational and structural dichotomies. SIAM J Comput 38:2330\u20132355","journal-title":"SIAM J Comput"},{"key":"9490_CR12","unstructured":"Hammer PL, Maffray F, Preismann M (1989) A characterization of chordal bipartite graphs. Tech rep, Rutgers University, New Brunswick, NJ"},{"key":"9490_CR13","doi-asserted-by":"crossref","first-page":"1054","DOI":"10.1016\/j.tcs.2010.12.005","volume":"412","author":"T Ito","year":"2010","unstructured":"Ito T, Demaine ED, Harvey NJA, Papadimitriou CH, Sideri M, Uehara R, Uno Y (2010) On the complexity of reconfiguration problems. Theor Comput Sci 412:1054\u20131065","journal-title":"Theor Comput Sci"},{"key":"9490_CR14","series-title":"Lecture notes in computer science","first-page":"56","volume-title":"Proceedings of the 21st international workshop on combinatorial algorithms (IWOCA 2010)","author":"M Kaminski","year":"2010","unstructured":"Kaminski M, Medvedev P, Milanic M (2010) Shortest paths between shortest paths and independent sets. In: Proceedings of the 21st international workshop on combinatorial algorithms (IWOCA 2010). Lecture notes in computer science, vol\u00a06460, pp\u00a056\u201367"},{"key":"9490_CR15","unstructured":"Pelsmajer MJ, Tokazy J, West DB (2004) New proofs for strongly chordal graphs and chordal bipartite graphs. Unpublished manuscript"},{"key":"9490_CR16","series-title":"Lecture notes in computer science","doi-asserted-by":"crossref","first-page":"993","DOI":"10.1007\/3-540-45465-9_85","volume-title":"Proceedings of the 29th international colloquium on automata, languages and programming (ICALP 2002)","author":"R Uehara","year":"2002","unstructured":"Uehara R (2002) Linear time algorithms on chordal bipartite and strongly chordal graphs. In: Proceedings of the 29th international colloquium on automata, languages and programming (ICALP 2002). Lecture notes in computer science, vol\u00a02380, pp\u00a0993\u20131004"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-012-9490-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-012-9490-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-012-9490-y","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,23]],"date-time":"2024-04-23T22:34:45Z","timestamp":1713911685000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-012-9490-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,4,26]]},"references-count":16,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2014,1]]}},"alternative-id":["9490"],"URL":"https:\/\/doi.org\/10.1007\/s10878-012-9490-y","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,4,26]]}}}