{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T21:40:13Z","timestamp":1775079613005,"version":"3.50.1"},"publisher-location":"Cham","reference-count":16,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030865924","type":"print"},{"value":"9783030865931","type":"electronic"}],"license":[{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021]]},"DOI":"10.1007\/978-3-030-86593-1_11","type":"book-chapter","created":{"date-parts":[[2021,9,11]],"date-time":"2021-09-11T20:26:28Z","timestamp":1631391988000},"page":"162-175","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Beyond the BEST Theorem: Fast Assessment of Eulerian Trails"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0770-2235","authenticated-orcid":false,"given":"Alessio","family":"Conte","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7985-4222","authenticated-orcid":false,"given":"Roberto","family":"Grossi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0888-5061","authenticated-orcid":false,"given":"Grigorios","family":"Loukides","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3915-7665","authenticated-orcid":false,"given":"Nadia","family":"Pisanti","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1445-1932","authenticated-orcid":false,"given":"Solon P.","family":"Pissis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8738-1595","authenticated-orcid":false,"given":"Giulia","family":"Punzi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,9,9]]},"reference":[{"key":"11_CR1","doi-asserted-by":"publisher","unstructured":"van Aardenne-Ehrenfest, T., de Bruijn, N.G.: Circuits and Trees in Oriented Linear Graphs, pp. 149\u2013163. Birkh\u00e4user Boston, Boston, MA (1987). https:\/\/doi.org\/10.1007\/978-0-8176-4842-8_12","DOI":"10.1007\/978-0-8176-4842-8_12"},{"key":"11_CR2","doi-asserted-by":"publisher","unstructured":"Alman, J., Williams, V.V.: A refined laser method and faster matrix multiplication. In: Marx, D. (ed.) Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, 10\u201313 January 2021, pp. 522\u2013539. SIAM (2021). https:\/\/doi.org\/10.1137\/1.9781611976465.32","DOI":"10.1137\/1.9781611976465.32"},{"key":"11_CR3","doi-asserted-by":"publisher","unstructured":"Bernardini, G., Chen, H., Fici, G., Loukides, G., Pissis, S.P.: Reverse-safe data structures for text indexing. In: Blelloch, G.E., Finocchi, I. (eds.) Proceedings of the Symposium on Algorithm Engineering and Experiments, ALENEX 2020, Salt Lake City, UT, USA, 5\u20136 January 2020. pp. 199\u2013213. SIAM (2020). https:\/\/doi.org\/10.1137\/1.9781611976007.16","DOI":"10.1137\/1.9781611976007.16"},{"key":"11_CR4","doi-asserted-by":"publisher","unstructured":"Bernstein, A., Probst, M., Wulff-Nilsen, C.: Decremental strongly-connected components and single-source reachability in near-linear time. In: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. p. 365\u2013376. STOC 2019, Association for Computing Machinery, New York, NY, USA (2019). https:\/\/doi.org\/10.1145\/3313276.3316335","DOI":"10.1145\/3313276.3316335"},{"key":"11_CR5","unstructured":"Biggs, N.L., Lloyd, E.K., Wilson, R.J.: Graph Theory 1736\u20131936. Clarendon Press (1976)"},{"key":"11_CR6","unstructured":"Brightwell, G.R., Winkler, P.: Counting Eulerian circuits is #P-complete. In: Demetrescu, C., Sedgewick, R., Tamassia, R. (eds.) Proceedings of the Seventh Workshop on Algorithm Engineering and Experiments and the Second Workshop on Analytic Algorithmics and Combinatorics, ALENEX\/ANALCO 2005, Vancouver, BC, Canada, 22 January 2005, pp. 259\u2013262. SIAM (2005), http:\/\/www.siam.org\/meetings\/analco05\/papers\/09grbrightwell.pdf"},{"issue":"3","key":"11_CR7","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1137\/0207024","volume":"7","author":"HN Gabow","year":"1978","unstructured":"Gabow, H.N., Myers, E.W.: Finding all spanning trees of directed and undirected graphs. SIAM J. Comput. 7(3), 280\u2013287 (1978)","journal-title":"SIAM J. Comput."},{"key":"11_CR8","doi-asserted-by":"publisher","unstructured":"Gall, F.L.: Powers of tensors and fast matrix multiplication. In: Nabeshima, K., Nagasaka, K., Winkler, F., Sz\u00e1nt\u00f3, \u00c1. (eds.) International Symposium on Symbolic and Algebraic Computation, ISSAC 2014, Kobe, Japan, July 23\u201325, 2014, pp. 296\u2013303. ACM (2014). https:\/\/doi.org\/10.1145\/2608628.2608664","DOI":"10.1145\/2608628.2608664"},{"issue":"1","key":"11_CR9","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1007\/BF01442866","volume":"6","author":"C Hierholzer","year":"1873","unstructured":"Hierholzer, C., Wiener, C.: \u00dcber die m\u00f6glichkeit, einen linienzug ohne wiederholung und ohne unterbrechung zu umfahren. Math. Ann. 6(1), 30\u201332 (1873)","journal-title":"Math. Ann."},{"issue":"1","key":"11_CR10","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1016\/0097-3165(75)90068-0","volume":"18","author":"JP Hutchinson","year":"1975","unstructured":"Hutchinson, J.P., Wilf, H.S.: On Eulerian circuits and words with prescribed adjacency patterns. J. Combin. Theor. Ser. A 18(1), 80\u201387 (1975)","journal-title":"J. Combin. Theor. Ser. A"},{"key":"11_CR11","doi-asserted-by":"publisher","unstructured":"Kingsford, C., Schatz, M.C., Pop, M.: Assembly complexity of prokaryotic genomes using short reads. BMC Bioinform. 11, 21 (2010). https:\/\/doi.org\/10.1186\/1471-2105-11-21","DOI":"10.1186\/1471-2105-11-21"},{"key":"11_CR12","doi-asserted-by":"publisher","unstructured":"Patro, R., Mount, S.M., Kingsford, C.: Sailfish: alignment-free isoform quantification from RNA-seq reads using lightweight algorithms. Nature Biotechnol. 32, 462\u2013464 (2014). https:\/\/doi.org\/10.1038\/nbt.2862, https:\/\/www.nature.com\/articles\/nbt.2862","DOI":"10.1038\/nbt.2862"},{"key":"11_CR13","unstructured":"Ruskey, F.: Combinatorial generation. Preliminary working draft. University of Victoria, Victoria, BC, Canada 11, 20 (2003)"},{"key":"11_CR14","doi-asserted-by":"publisher","unstructured":"Tarjan, R.E.: Depth-first search and linear graph algorithms. SIAM J. Comput. 1(2), 146\u2013160 (1972). https:\/\/doi.org\/10.1137\/0201010, https:\/\/doi.org\/10.1137\/0201010","DOI":"10.1137\/0201010"},{"key":"11_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1007\/3-540-48686-0_35","volume-title":"Comput. Combin.","author":"Takeaki Uno","year":"1999","unstructured":"Uno, Takeaki: A new approach for speeding up enumeration algorithms and its application for matroid bases. In: Asano, Takano, Imai, Hideki, Lee, D.. T.., Nakano, Shin-ichi, Tokuyama, Takeshi (eds.) COCOON 1999. LNCS, vol. 1627, pp. 349\u2013359. Springer, Heidelberg (1999). https:\/\/doi.org\/10.1007\/3-540-48686-0_35"},{"key":"11_CR16","doi-asserted-by":"publisher","unstructured":"Williams, V.V.: Multiplying matrices faster than coppersmith-winograd. In: Karloff, H.J., Pitassi, T. (eds.) Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, 19\u201322 May 2012, pp. 887\u2013898. ACM (2012). https:\/\/doi.org\/10.1145\/2213977.2214056","DOI":"10.1145\/2213977.2214056"}],"container-title":["Lecture Notes in Computer Science","Fundamentals of Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-86593-1_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,11]],"date-time":"2021-09-11T20:29:56Z","timestamp":1631392196000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-86593-1_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"ISBN":["9783030865924","9783030865931"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-86593-1_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021]]},"assertion":[{"value":"9 September 2021","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"FCT","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Symposium on Fundamentals of Computation Theory","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Athens","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Greece","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2021","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"12 September 2021","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15 September 2021","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"fct2021","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/www.corelab.ntua.gr\/fct2021\/","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":"94","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":"32% - 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":"3","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":"8.54","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)"}},{"value":"The conference was held virtually due to the COVID-19 pandemic. There are papers of 2 invited talks also included.","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}