{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:28:39Z","timestamp":1759638519870,"version":"3.40.3"},"publisher-location":"Cham","reference-count":30,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030002558"},{"type":"electronic","value":"9783030002565"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"unspecified","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":[[2018]]},"DOI":"10.1007\/978-3-030-00256-5_5","type":"book-chapter","created":{"date-parts":[[2018,9,1]],"date-time":"2018-09-01T08:22:08Z","timestamp":1535790128000},"page":"52-64","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Recognizing Hyperelliptic Graphs in Polynomial Time"],"prefix":"10.1007","author":[{"given":"Jelco M.","family":"Bodewes","sequence":"first","affiliation":[]},{"given":"Hans L.","family":"Bodlaender","sequence":"additional","affiliation":[]},{"given":"Gunther","family":"Cornelissen","sequence":"additional","affiliation":[]},{"given":"Marieke","family":"van der Wegen","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,9,2]]},"reference":[{"issue":"2","key":"5_CR1","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1137\/0607033","volume":"7","author":"S Arnborg","year":"1986","unstructured":"Arnborg, S., Proskurowski, A.: Characterization and recognition of partial $$3$$-trees. SIAM J. Algebraic Discrete Methods 7(2), 305\u2013314 (1986)","journal-title":"SIAM J. Algebraic Discrete Methods"},{"key":"5_CR2","doi-asserted-by":"crossref","unstructured":"Babai, L.: Graph isomorphism in quasipolynomial time. Preprint arXiv: 1512.03547v2 (2016)","DOI":"10.1145\/2897518.2897542"},{"key":"5_CR3","doi-asserted-by":"crossref","unstructured":"Bak, P., Tang, C., Wiesenfeld, K.: Self-organized criticality. Phys. Rev. A 38(1), 364 (1988)","DOI":"10.1103\/PhysRevA.38.364"},{"key":"5_CR4","doi-asserted-by":"crossref","unstructured":"Baker, M.: Specialization of linear systems from curves to graphs. Algebra Number Theory 2(6), 613\u2013653 (2008). With an appendix by Brian Conrad","DOI":"10.2140\/ant.2008.2.613"},{"key":"5_CR5","first-page":"2914","volume":"15","author":"M Baker","year":"2009","unstructured":"Baker, M., Norine, S.: Harmonic morphisms and hyperelliptic graphs. Int. Math. Res. Not. IMRN 15, 2914\u20132955 (2009)","journal-title":"Int. Math. Res. Not. IMRN"},{"issue":"1","key":"5_CR6","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1016\/j.jcta.2012.07.011","volume":"120","author":"M Baker","year":"2013","unstructured":"Baker, M., Shokrieh, F.: Chip-firing games, potential theory on graphs, and spanning trees. J. Comb. Theory Ser. A 120(1), 164\u2013182 (2013)","journal-title":"J. Comb. Theory Ser. A"},{"key":"5_CR7","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1016\/0196-6774(91)90003-H","volume":"12","author":"D Bienstock","year":"1991","unstructured":"Bienstock, D., Seymour, P.: Monotonicity in graph searching. J. Algorithms 12, 239\u2013245 (1991)","journal-title":"J. Algorithms"},{"issue":"4","key":"5_CR8","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1016\/S0195-6698(13)80111-4","volume":"12","author":"A Bj\u00f6rner","year":"1991","unstructured":"Bj\u00f6rner, A., Lov\u00e1sz, L., Shor, P.W.: Chip-firing games on graphs. European J. Combin 12(4), 283\u2013291 (1991)","journal-title":"European J. Combin"},{"key":"5_CR9","doi-asserted-by":"crossref","unstructured":"Bodewes, J.M., Bodlaender, H.L., Cornelissen, G., van der Wegen, M.: Recognizing hyperelliptic graphs in polynomial time. Preprint arXiv: 1706.05670 (2017)","DOI":"10.1007\/978-3-030-00256-5_5"},{"issue":"2","key":"5_CR10","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1137\/130947374","volume":"45","author":"HL Bodlaender","year":"2016","unstructured":"Bodlaender, H.L., Drange, P.G., Dregi, M.S., Fomin, F.V., Lokshtanov, D., Pilipczuk, M.: A $$c^k n$$ 5-approximation algorithm for treewidth. SIAM J. Comput. 45(2), 317\u2013378 (2016)","journal-title":"SIAM J. Comput."},{"issue":"6","key":"5_CR11","doi-asserted-by":"publisher","first-page":"1725","DOI":"10.1137\/S0097539795289859","volume":"27","author":"HL Bodlaender","year":"1998","unstructured":"Bodlaender, H.L., Hagerup, T.: Parallel algorithms with optimal speedup for bounded treewidth. SIAM J. Comput. 27(6), 1725\u20131746 (1998)","journal-title":"SIAM J. Comput."},{"issue":"7","key":"5_CR12","doi-asserted-by":"publisher","first-page":"1103","DOI":"10.1016\/j.ic.2011.04.003","volume":"209","author":"HL Bodlaender","year":"2011","unstructured":"Bodlaender, H.L., Koster, A.M.C.A.: Treewidth computations II. Lower bounds. Inform. and Comput. 209(7), 1103\u20131119 (2011)","journal-title":"Inform. and Comput."},{"issue":"3\u20134","key":"5_CR13","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1006\/jsco.1996.0125","volume":"24","author":"W Bosma","year":"1997","unstructured":"Bosma, W., Cannon, J., Playoust, C.: The Magma algebra system. I. The user language. J. Symbolic Comput. 24(3\u20134), 235\u2013265 (1997)","journal-title":"J. Symbolic Comput."},{"issue":"1","key":"5_CR14","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1137\/140982015","volume":"29","author":"M Chan","year":"2015","unstructured":"Chan, M., Glass, D., Macauley, M., Perkinson, D., Werner, C., Yang, Q.: Sandpiles, spanning trees, and plane duality. SIAM J. Discrete Math. 29(1), 461\u2013471 (2015)","journal-title":"SIAM J. Discrete Math."},{"key":"5_CR15","unstructured":"Cohen, H., et al.: Handbook of Elliptic and Hyperelliptic Curve Cryptography, Second Edn. Chapman & Hall\/CRC, Boca Raton (2012)"},{"issue":"1\u20132","key":"5_CR16","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1007\/s00208-014-1067-x","volume":"361","author":"G Cornelissen","year":"2015","unstructured":"Cornelissen, G., Kato, F., Kool, J.: A combinatorial Li-Yau inequality and rational points on curves. Math. Ann. 361(1\u20132), 211\u2013258 (2015)","journal-title":"Math. Ann."},{"issue":"1","key":"5_CR17","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","volume":"85","author":"B Courcelle","year":"1990","unstructured":"Courcelle, B.: The monadic second-order logic of graphs. I: recognizable sets of finite graphs. Inform. and Comput. 85(1), 12\u201375 (1990)","journal-title":"Inform. and Comput."},{"issue":"1","key":"5_CR18","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1016\/S0166-218X(02)00421-3","volume":"131","author":"B Courcelle","year":"2003","unstructured":"Courcelle, B., Vanicat, R.: Query efficient implementation of graphs of bounded clique-width. Discrete Appl. Math. 131(1), 129\u2013150 (2003)","journal-title":"Discrete Appl. Math."},{"key":"5_CR19","doi-asserted-by":"crossref","unstructured":"Dhar, D.: Self-organized critical state of sandpile automaton models. Phys. Rev. Let. 64(14), 1613 (1990)","DOI":"10.1103\/PhysRevLett.64.1613"},{"key":"5_CR20","unstructured":"van Dobben de Bruyn, J.: Reduced divisors and gonality in finite graphs. Bachelor thesis, Leiden University (2012). https:\/\/www.universiteitleiden.nl\/binaries\/content\/assets\/science\/mi\/scripties\/bachvandobbendebruyn.pdf"},{"key":"5_CR21","unstructured":"van Dobben de Bruyn, J., Gijswijt, D.: Treewidth is a lower bound on graph gonality. Preprint arXiv:1407.7055 (2014)"},{"key":"5_CR22","unstructured":"Gijswijt, D.: Computing divisorial gonality is hard. Preprint arXiv:1504.06713 (2015)"},{"issue":"3","key":"5_CR23","doi-asserted-by":"publisher","first-page":"292","DOI":"10.1007\/s004530010021","volume":"27","author":"T Hagerup","year":"2000","unstructured":"Hagerup, T.: Dynamic algorithms for graphs of bounded treewidth. Algorithmica 27(3), 292\u2013315 (2000)","journal-title":"Algorithmica"},{"key":"5_CR24","unstructured":"Hendrey, K.: Sparse graphs of high gonality. Preprint arXiv:1606.06412 (2016)"},{"issue":"2","key":"5_CR25","doi-asserted-by":"publisher","first-page":"224","DOI":"10.1145\/151261.151263","volume":"40","author":"AS LaPaugh","year":"1993","unstructured":"LaPaugh, A.S.: Recontamination does not help to search a graph. J. ACM 40(2), 224\u2013245 (1993)","journal-title":"J. ACM"},{"issue":"1","key":"5_CR26","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1137\/0210002","volume":"10","author":"A Lubiw","year":"1981","unstructured":"Lubiw, A.: Some NP-complete problems similar to graph isomorphism. SIAM J. Comput. 10(1), 11\u201321 (1981)","journal-title":"SIAM J. Comput."},{"key":"5_CR27","doi-asserted-by":"crossref","unstructured":"Norin, S.: New tools and results in graph minor structure theory. In: Surveys in Combinatorics 2015. London Mathematical Society Lecture Note Series, vol. 424, pp. 221\u2013260. Cambridge University Press (2015)","DOI":"10.1017\/CBO9781316106853.008"},{"key":"5_CR28","doi-asserted-by":"crossref","unstructured":"Poonen, B.: Computing rational points on curves. Number theory for the millennium. III (Urbana, IL, 2000), pp. 149\u2013172. A K Peters, Natick (2002)","DOI":"10.1201\/9780138747022-9"},{"issue":"5","key":"5_CR29","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1007\/s00200-013-0205-0","volume":"24","author":"J Schicho","year":"2013","unstructured":"Schicho, J., Schreyer, F.-O., Weimann, M.: Computational aspects of gonal maps and radical parametrization of curves. Appl. Algebra Engrg. Comm. Comput. 24(5), 313\u2013341 (2013)","journal-title":"Appl. Algebra Engrg. Comm. Comput."},{"issue":"3","key":"5_CR30","doi-asserted-by":"publisher","first-page":"397","DOI":"10.1137\/0401039","volume":"1","author":"G Tardos","year":"1988","unstructured":"Tardos, G.: Polynomial bound for a chip firing game on graphs. SIAM J. Discrete Math. 1(3), 397\u2013398 (1988)","journal-title":"SIAM J. Discrete Math."}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-00256-5_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,13]],"date-time":"2024-03-13T13:24:16Z","timestamp":1710336256000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-00256-5_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783030002558","9783030002565"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-00256-5_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"value":"2 September 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WG","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Graph-Theoretic Concepts in Computer Science","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Cottbus","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Germany","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2018","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27 June 2018","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"29 June 2018","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"44","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wg2018","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/www.wg2018.b-tu.de\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"66","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"30","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"45% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"4","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"11,5","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}