{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T14:48:39Z","timestamp":1742914119993,"version":"3.40.3"},"publisher-location":"Cham","reference-count":34,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030247652"},{"type":"electronic","value":"9783030247669"}],"license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019]]},"DOI":"10.1007\/978-3-030-24766-9_22","type":"book-chapter","created":{"date-parts":[[2019,7,30]],"date-time":"2019-07-30T23:09:48Z","timestamp":1564528188000},"page":"296-310","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Kernelization of Graph Hamiltonicity: Proper H-Graphs"],"prefix":"10.1007","author":[{"given":"Steven","family":"Chaplick","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fedor V.","family":"Fomin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Petr A.","family":"Golovach","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Du\u0161an","family":"Knop","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peter","family":"Zeman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,7,12]]},"reference":[{"issue":"4","key":"22_CR1","doi-asserted-by":"publisher","first-page":"844","DOI":"10.1145\/210332.210337","volume":"42","author":"N Alon","year":"1995","unstructured":"Alon, N., Yuster, R., Zwick, U.: Color-coding. J. ACM 42(4), 844\u2013856 (1995)","journal-title":"J. ACM"},{"issue":"2","key":"22_CR2","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/0020-0190(83)90078-9","volume":"17","author":"AA Bertossi","year":"1983","unstructured":"Bertossi, A.A.: Finding Hamiltonian circuits in proper interval graphs. Inf. Process. Lett. 17(2), 97\u2013101 (1983)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"22_CR3","first-page":"267","volume":"100","author":"M Biro","year":"1992","unstructured":"Biro, M., Hujter, M., Tuza, Z.: Precoloring extension. I. Interval graphs. Discrete Math. 100(1), 267\u2013279 (1992)","journal-title":"I. Interval graphs. Discrete Math."},{"key":"22_CR4","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Kaski, P., Koivisto, M.: Narrow sieves for parameterized paths and packings. CoRR abs\/1007.1161 (2010)"},{"issue":"8","key":"22_CR5","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1016\/j.jcss.2009.04.001","volume":"75","author":"HL Bodlaender","year":"2009","unstructured":"Bodlaender, H.L., Downey, R.G., Fellows, M.R., Hermelin, D.: On problems without polynomial kernels. J. Comput. Syst. Sci. 75(8), 423\u2013434 (2009)","journal-title":"J. Comput. Syst. Sci."},{"key":"22_CR6","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1016\/j.tcs.2012.09.006","volume":"511","author":"HL Bodlaender","year":"2013","unstructured":"Bodlaender, H.L., Jansen, B.M.P., Kratsch, S.: Kernel bounds for path and cycle problems. Theor. Comput. Sci. 511, 117\u2013136 (2013)","journal-title":"Theor. Comput. Sci."},{"issue":"5","key":"22_CR7","doi-asserted-by":"publisher","first-page":"1662","DOI":"10.1137\/S0097539799357775","volume":"30","author":"A Brandst\u00e4dt","year":"2000","unstructured":"Brandst\u00e4dt, A., Dragan, F.F., K\u00f6hler, E.: Linear time algorithms for hamiltonian problems on (claw, net)-free graphs. SIAM J. Comput. 30(5), 1662\u20131677 (2000)","journal-title":"SIAM J. Comput."},{"key":"22_CR8","doi-asserted-by":"crossref","unstructured":"Brandst\u00e4dt, A., Le, V.B., Spinrad, J.P.: Graph Classes: A Survey. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, SIAM Monographs on Discrete Mathematics and Applications (1999)","DOI":"10.1137\/1.9780898719796"},{"key":"22_CR9","doi-asserted-by":"publisher","first-page":"282","DOI":"10.1002\/jgt.21832","volume":"79","author":"H Broersma","year":"2015","unstructured":"Broersma, H., Fiala, J., Golovach, P.A., Kaiser, T., Paulusma, D., Proskurowski, A.: Linear-time algorithms for scattering number and hamilton-connectivity of interval graphs. J. Graph Theor. 79, 282\u2013299 (2015)","journal-title":"J. Graph Theor."},{"issue":"1","key":"22_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1002\/(SICI)1097-0037(199908)34:1<1::AID-NET1>3.0.CO;2-C","volume":"34","author":"M Chang","year":"1999","unstructured":"Chang, M., Peng, S., Liaw, J.: Deferred-query: an efficient approach for some problems on interval graphs. Networks 34(1), 1\u201310 (1999)","journal-title":"Networks"},{"key":"22_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1007\/978-3-319-68705-6_13","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"S Chaplick","year":"2017","unstructured":"Chaplick, S., T\u00f6pfer, M., Voborn\u00edk, J., Zeman, P.: On H-topological intersection graphs. In: Bodlaender, H.L., Woeginger, G.J. (eds.) WG 2017. LNCS, vol. 10520, pp. 167\u2013179. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-68705-6_13"},{"key":"22_CR12","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1016\/j.endm.2017.06.042","volume":"61","author":"Steven Chaplick","year":"2017","unstructured":"Chaplick, S., Zeman, P.: Combinatorial problems on H-graphs. In: EUROCOMB, vol. 61, ENDM, pp. 223\u2013229 (2017). arXiv:1706.00575","journal-title":"Electronic Notes in Discrete Mathematics"},{"issue":"1\u20133","key":"22_CR13","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1016\/S0012-365X(96)00307-X","volume":"170","author":"C Chen","year":"1997","unstructured":"Chen, C., Chang, C., Chang, G.J.: Proper interval graphs and the guard problem. Discrete Math. 170(1\u20133), 223\u2013230 (1997)","journal-title":"Discrete Math."},{"key":"22_CR14","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., et al.: Parameterized Algorithms. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-21275-3"},{"key":"22_CR15","doi-asserted-by":"crossref","unstructured":"Cygan, M., Nederlof, J., Pilipczuk, M., Pilipczuk, M., van Rooij, J.M.M., Wojtaszczyk, J.O.: Solving connectivity problems parameterized by treewidth in single exponential time. In: FOCS 2011, pp. 150\u2013159. IEEE (2011)","DOI":"10.1109\/FOCS.2011.23"},{"issue":"1\u20133","key":"22_CR16","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/0012-365X(93)90223-G","volume":"112","author":"P Damaschke","year":"1993","unstructured":"Damaschke, P.: Paths in interval graphs and circular arc graphs. Discrete Math. 112(1\u20133), 49\u201364 (1993)","journal-title":"Discrete Math."},{"key":"22_CR17","series-title":"Texts in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of Parameterized Complexity","author":"RG Downey","year":"2013","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, London (2013). https:\/\/doi.org\/10.1007\/978-1-4471-5559-1"},{"key":"22_CR18","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.jcss.2016.06.004","volume":"84","author":"M Etscheid","year":"2017","unstructured":"Etscheid, M., Kratsch, S., Mnich, M., R\u00f6glin, H.: Polynomial kernels for weighted problems. J. Comput. Syst. Sci. 84, 1\u201310 (2017)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"22_CR19","doi-asserted-by":"publisher","first-page":"822","DOI":"10.1007\/s00224-009-9167-9","volume":"45","author":"MR Fellows","year":"2009","unstructured":"Fellows, M.R., Lokshtanov, D., Misra, N., Mnich, M., Rosamond, F.A., Saurabh, S.: The complexity ecology of parameters: an illustration using bounded max leaf number. Theory Comput. Syst. 45(4), 822\u2013848 (2009)","journal-title":"Theory Comput. Syst."},{"key":"22_CR20","unstructured":"Fomin, F.V., Golovach, P.A., Raymond, J.: On the tractability of optimization problems on H-graphs. In: ESA 2018, vol. 112 of LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, pp. 30:1\u201330:14 (2018)"},{"key":"22_CR21","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Lokshtanov, D., Saurabh, S., Zehavi, M.: Kernelization. In: Theory of Parameterized Preprocessing, Cambridge University Press (2019)","DOI":"10.1017\/9781107415157"},{"issue":"1","key":"22_CR22","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/BF02579200","volume":"7","author":"A Frank","year":"1987","unstructured":"Frank, A., Tardos, \u00c9.: An application of simultaneous diophantine approximation in combinatorial optimization. Combinatorica 7(1), 49\u201365 (1987)","journal-title":"Combinatorica"},{"key":"22_CR23","unstructured":"Garey, M.R., Johnson, D.S.: Computers and intractability. In: Computers and Intractability: A Guide to the Theory of NP-Completeness, A Series of Books in the Mathematical Sciences. W. H. Freeman & Co. (1979)"},{"key":"22_CR24","doi-asserted-by":"crossref","unstructured":"Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs, Annals of Discrete Mathematics, vol. 57, 2nd edn. Elsevier Science B.V., Amsterdam (2004). With a foreword by Claude Berge","DOI":"10.1016\/S0167-5060(04)80051-7"},{"issue":"5","key":"22_CR25","doi-asserted-by":"publisher","first-page":"648","DOI":"10.1016\/j.aml.2010.11.030","volume":"24","author":"R Hung","year":"2011","unstructured":"Hung, R., Chang, M.: Linear-time certifying algorithms for the path cover and hamiltonian cycle problems on interval graphs. Appl. Math. Lett. 24(5), 648\u2013652 (2011)","journal-title":"Appl. Math. Lett."},{"issue":"18","key":"22_CR26","doi-asserted-by":"publisher","first-page":"1105","DOI":"10.1016\/j.ipl.2009.07.010","volume":"109","author":"L Ibarra","year":"2009","unstructured":"Ibarra, L.: A simple algorithm to find Hamiltonian cycles in proper interval graphs. Inf. Process. Lett. 109(18), 1105\u20131108 (2009)","journal-title":"Inf. Process. Lett."},{"issue":"4","key":"22_CR27","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1016\/0020-0190(85)90050-X","volume":"20","author":"JM Keil","year":"1985","unstructured":"Keil, J.M.: Finding hamiltonian circuits in interval graphs. Inf. Process. Lett. 20(4), 201\u2013206 (1985)","journal-title":"Inf. Process. Lett."},{"key":"22_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"575","DOI":"10.1007\/978-3-540-70575-8_47","volume-title":"Automata, Languages and Programming","author":"I Koutis","year":"2008","unstructured":"Koutis, I.: Faster algebraic algorithms for path and packing problems. In: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) ICALP 2008. LNCS, vol. 5125, pp. 575\u2013586. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-70575-8_47"},{"key":"22_CR29","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1016\/j.dam.2017.04.045","volume":"248","author":"M Lampis","year":"2018","unstructured":"Lampis, M., Makino, K., Mitsou, V., Uno, Y.: Parameterized edge hamiltonicity. Discrete Appl. Math. 248, 68\u201378 (2018)","journal-title":"Discrete Appl. Math."},{"issue":"4","key":"22_CR30","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/0020-0190(90)90025-S","volume":"35","author":"GK Manacher","year":"1990","unstructured":"Manacher, G.K., Mankus, T.A., Smith, C.J.: An optimum theta (n log n) algorithm for finding a canonical hamiltonian path and a canonical hamiltonian circuit in a set of intervals. Inf. Process. Lett. 35(4), 205\u2013211 (1990)","journal-title":"Inf. Process. Lett."},{"issue":"1\u20133","key":"22_CR31","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1016\/0012-365X(95)00057-4","volume":"156","author":"H M\u00fcller","year":"1996","unstructured":"M\u00fcller, H.: Hamiltonian circuits in chordal bipartite graphs. Discrete Math. 156(1\u20133), 291\u2013298 (1996)","journal-title":"Discrete Math."},{"key":"22_CR32","unstructured":"Roberts, F.S.: Indifference graphs. In: Proof Techniques in Graph Theory (Proceedings of the Second Ann Arbor Graph Theory Conference, Ann Arbor, Michigan, 1968), pp. 139\u2013146. Academic Press, New York (1969)"},{"issue":"6","key":"22_CR33","doi-asserted-by":"publisher","first-page":"1026","DOI":"10.1137\/0221061","volume":"21","author":"W Shih","year":"1992","unstructured":"Shih, W., Chern, T.C., Hsu, W.: An o(n$${^2}$$ log n) algorithm for the hamiltonian cycle problem on circular-arc graphs. SIAM J. Comput. 21(6), 1026\u20131046 (1992)","journal-title":"SIAM J. Comput."},{"issue":"6","key":"22_CR34","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1016\/j.ipl.2008.11.004","volume":"109","author":"R Williams","year":"2009","unstructured":"Williams, R.: Finding paths of length $$k$$ in $$O(2^k)$$ time. Inf. Process. Lett. 109(6), 315\u2013318 (2009)","journal-title":"Inf. Process. Lett."}],"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-030-24766-9_22","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,12]],"date-time":"2024-03-12T17:54:09Z","timestamp":1710266049000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-24766-9_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783030247652","9783030247669"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-24766-9_22","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2019]]},"assertion":[{"value":"12 July 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WADS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Workshop on Algorithms and Data Structures","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Edmonton, AB","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Canada","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2019","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"5 August 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"7 August 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wads2019","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/www.wads.org\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}