{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T13:11:51Z","timestamp":1725541911793},"publisher-location":"Berlin, Heidelberg","reference-count":13,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642112652"},{"type":"electronic","value":"9783642112669"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-11266-9_42","type":"book-chapter","created":{"date-parts":[[2009,12,7]],"date-time":"2009-12-07T09:04:58Z","timestamp":1260176698000},"page":"503-514","source":"Crossref","is-referenced-by-count":4,"title":["On Contracting Graphs to Fixed Pattern Graphs"],"prefix":"10.1007","author":[{"given":"Pim","family":"van \u2019t Hof","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marcin","family":"Kami\u0144ski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dani\u00ebl","family":"Paulusma","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stefan","family":"Szeider","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dimitrios M.","family":"Thilikos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"42_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1007\/11809678_22","volume-title":"Computing and Combinatorics","author":"M. Andersson","year":"2006","unstructured":"Andersson, M., Gudmundsson, J., Levcopoulos, C.: Restricted Mesh Simplification Using Edge Contraction. In: Chen, D.Z., Lee, D.T. (eds.) COCOON 2006. LNCS, vol.\u00a04112, pp. 196\u2013204. Springer, Heidelberg (2006)"},{"key":"42_CR2","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1002\/jgt.3190110111","volume":"11","author":"A.E. Brouwer","year":"1987","unstructured":"Brouwer, A.E., Veldman, H.J.: Contractibility and NP-Completeness. Journal of Graph Theory\u00a011, 71\u201379 (1987)","journal-title":"Journal of Graph Theory"},{"key":"42_CR3","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1016\/j.comgeo.2003.07.001","volume":"27","author":"S. Cheng","year":"2004","unstructured":"Cheng, S., Dey, T., Poon, S.: Hierarchy of Surface Models and Irreducible Triangulations. Computational Geometry Theory and Applications\u00a027, 135\u2013150 (2004)","journal-title":"Computational Geometry Theory and Applications"},{"key":"42_CR4","doi-asserted-by":"publisher","first-page":"346","DOI":"10.1109\/TCAD.2004.823353","volume":"23","author":"J. Cong","year":"2004","unstructured":"Cong, J., Lim, S.K.: Edge Separability-Based Circuit Clustering with Application to Multilevel Circuit Partitioning. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems\u00a023, 346\u2013357 (2004)","journal-title":"IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems"},{"key":"42_CR5","series-title":"Monographs in Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Monographs in Computer Science. Springer, Heidelberg (1999)"},{"key":"42_CR6","doi-asserted-by":"publisher","first-page":"266","DOI":"10.1007\/BF01190507","volume":"13","author":"M.R. Fellows","year":"1995","unstructured":"Fellows, M.R., Kratochv\u00edl, J., Middendorf, M., Pfeiffer, F.: The Complexity of Induced Minors and Related Problems. Algorithmica\u00a013, 266\u2013282 (1995)","journal-title":"Algorithmica"},{"key":"42_CR7","volume-title":"Computers and Intractability","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability. W.H.\u00a0Freeman and Co., New York (1979)"},{"key":"42_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1007\/3-540-45294-X_3","volume-title":"FST TCS 2001: Foundations of Software Technology and Theoretical Computer Science","author":"D. Harel","year":"2001","unstructured":"Harel, D., Koren, Y.: On Clustering Using Random Walks. In: Hariharan, R., Mukund, M., Vinay, V. (eds.) FSTTCS 2001. LNCS, vol.\u00a02245, pp. 18\u201341. Springer, Heidelberg (2001)"},{"key":"42_CR9","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1016\/0012-365X(81)90022-4","volume":"34","author":"C. Hoede","year":"1981","unstructured":"Hoede, C., Veldman, H.J.: Contraction Theorems in Hamiltonian Graph Theory. Discrete Mathematics\u00a034, 61\u201367 (1981)","journal-title":"Discrete Mathematics"},{"key":"42_CR10","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1137\/S1064827595287997","volume":"20","author":"G. Karypis","year":"1999","unstructured":"Karypis, G., Kumar, V.: A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs. SIAM Journal on Scientific Computing\u00a020, 359\u2013392 (1999)","journal-title":"SIAM Journal on Scientific Computing"},{"key":"42_CR11","doi-asserted-by":"publisher","first-page":"178","DOI":"10.1002\/net.20214","volume":"51","author":"A. Levin","year":"2008","unstructured":"Levin, A., Paulusma, D., Woeginger, G.J.: The Computational Complexity of Graph Contractions\u00a0I: Polynomially Solvable and NP-Complete Cases. Networks\u00a051, 178\u2013189 (2008)","journal-title":"Networks"},{"key":"42_CR12","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1002\/net.20249","volume":"52","author":"A. Levin","year":"2008","unstructured":"Levin, A., Paulusma, D., Woeginger, G.J.: The Computational Complexity of Graph Contractions\u00a0II: Two Tough Polynomially Solvable Cases. Networks\u00a052, 32\u201356 (2008)","journal-title":"Networks"},{"key":"42_CR13","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1006\/jctb.1995.1006","volume":"63","author":"N. Robertson","year":"1995","unstructured":"Robertson, N., Seymour, P.D.: Graph Minors. XIII. The Disjoint Paths Problem. Journal of Combinatorial Theory, Series\u00a0B\u00a063, 65\u2013110 (1995)","journal-title":"Journal of Combinatorial Theory, Series\u00a0B"}],"container-title":["Lecture Notes in Computer Science","SOFSEM 2010: Theory and Practice of Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-11266-9_42","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,10]],"date-time":"2019-03-10T18:59:51Z","timestamp":1552244391000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-11266-9_42"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642112652","9783642112669"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-11266-9_42","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}