{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T08:41:52Z","timestamp":1758271312826,"version":"3.40.5"},"reference-count":20,"publisher":"Elsevier BV","license":[{"start":{"date-parts":[[2016,3,1]],"date-time":"2016-03-01T00:00:00Z","timestamp":1456790400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2016,5,13]],"date-time":"2016-05-13T00:00:00Z","timestamp":1463097600000},"content-version":"vor","delay-in-days":73,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001665","name":"ANR","doi-asserted-by":"publisher","award":["ANR-12-BS02-0008","ANR-11-BINF-0002"],"award-info":[{"award-number":["ANR-12-BS02-0008","ANR-11-BINF-0002"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001665","name":"ANR","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004794","name":"CNRS","doi-asserted-by":"publisher","award":["D\u00e9fi MASTODONS"],"award-info":[{"award-number":["D\u00e9fi MASTODONS"]}],"id":[{"id":"10.13039\/501100004794","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Journal of Discrete Algorithms"],"published-print":{"date-parts":[[2016,3]]},"DOI":"10.1016\/j.jda.2016.05.001","type":"journal-article","created":{"date-parts":[[2016,5,20]],"date-time":"2016-05-20T18:40:23Z","timestamp":1463769623000},"page":"56-67","update-policy":"https:\/\/doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":5,"special_numbering":"C","title":["A linear time algorithm for Shortest Cyclic Cover of Strings"],"prefix":"10.1016","volume":"37","author":[{"given":"Bastien","family":"Cazaux","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3791-3973","authenticated-orcid":false,"given":"Eric","family":"Rivals","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/j.jda.2016.05.001_br0010","series-title":"ACM Symposium on the Theory of Computing","first-page":"328","article-title":"Linear approximation of shortest superstrings","author":"Blum","year":"1991"},{"key":"10.1016\/j.jda.2016.05.001_br0020","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1016\/j.tcs.2012.07.018","article-title":"On suffix extensions in suffix trees","volume":"457","author":"Breslauer","year":"2012","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"10.1016\/j.jda.2016.05.001_br0030","doi-asserted-by":"crossref","first-page":"340","DOI":"10.1006\/jagm.1997.0861","article-title":"Rotations of periodic strings and short superstrings","volume":"24","author":"Breslauer","year":"1997","journal-title":"J. Algorithms"},{"key":"10.1016\/j.jda.2016.05.001_br0040","series-title":"Proc. of Prague Stringology Conference","first-page":"148","article-title":"Approximation of greedy algorithms for Max-ATSP, Maximal Compression, Maximal Cycle Cover, and Shortest Cyclic Cover of Strings","author":"Cazaux","year":"2014"},{"key":"10.1016\/j.jda.2016.05.001_br0050","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1016\/j.jda.2014.07.002","article-title":"Reverse engineering of compact suffix trees and links: a novel algorithm","volume":"28","author":"Cazaux","year":"2014","journal-title":"J. Discret. Algorithms"},{"key":"10.1016\/j.jda.2016.05.001_br0060","article-title":"The power of greedy algorithms for approximating Max-ATSP, Cyclic Cover, and superstrings","author":"Cazaux","year":"2015","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/j.jda.2016.05.001_br0070","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1016\/0022-0000(80)90004-5","article-title":"On finding minimal length superstrings","volume":"20","author":"Gallant","year":"1980","journal-title":"J. Comput. Syst. Sci."},{"key":"10.1016\/j.jda.2016.05.001_br0080","series-title":"Combinatorial Pattern Matching","first-page":"120","article-title":"Approximating shortest superstring problem using de Bruijn Graphs","volume":"vol. 7922","author":"Golovnev","year":"2013"},{"issue":"5","key":"10.1016\/j.jda.2016.05.001_br0090","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1016\/0020-0190(94)00097-2","article-title":"Faster implementation of a shortest superstring approximation","volume":"51","author":"Gusfield","year":"1994","journal-title":"Inf. Process. Lett."},{"year":"1997","series-title":"Algorithms on Strings, Trees and Sequences","author":"Gusfield","key":"10.1016\/j.jda.2016.05.001_br0100"},{"issue":"4","key":"10.1016\/j.jda.2016.05.001_br0110","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1016\/0020-0190(92)90176-V","article-title":"An efficient algorithm for the all pairs suffix\u2013prefix problem","volume":"41","author":"Gusfield","year":"1992","journal-title":"Inf. Process. Lett."},{"key":"10.1016\/j.jda.2016.05.001_br0120","series-title":"Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing","first-page":"169","article-title":"Large-scale assembly of DNA strings and space-efficient construction of suffix trees","author":"Kosaraju","year":"1995"},{"key":"10.1016\/j.jda.2016.05.001_br0130","series-title":"Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing","first-page":"659","article-title":"Large-scale assembly of DNA strings and space-efficient construction of suffix trees","author":"Kosaraju","year":"1996"},{"key":"10.1016\/j.jda.2016.05.001_br0140","series-title":"Proceedings of the Twenty-Fourth Annual ACM\u2013SIAM Symposium on Discrete Algorithms","first-page":"958","article-title":"Lyndon words and short superstrings","author":"Mucha","year":"2013"},{"author":"Paluch","key":"10.1016\/j.jda.2016.05.001_br0150"},{"year":"1998","series-title":"Combinatorial Optimization: Algorithms and Complexity","author":"Papadimitriou","key":"10.1016\/j.jda.2016.05.001_br0160"},{"key":"10.1016\/j.jda.2016.05.001_br0170","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1016\/0304-3975(88)90167-3","article-title":"A greedy approximation algorithm for constructing shortest common superstrings","volume":"57","author":"Tarhio","year":"1988","journal-title":"Theor. Comp. Sci."},{"key":"10.1016\/j.jda.2016.05.001_br0180","series-title":"34th Annual Symposium on Foundations of Computer Science","first-page":"158","article-title":"Approximating shortest superstrings","author":"Teng","year":"1993"},{"issue":"1\u20134","key":"10.1016\/j.jda.2016.05.001_br0190","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1007\/BF01840391","article-title":"A linear-time algorithm for finding approximate shortest common superstrings","volume":"5","author":"Ukkonen","year":"1990","journal-title":"Algorithmica"},{"key":"10.1016\/j.jda.2016.05.001_br0200","series-title":"Mathematical Foundations of Computer Science 2005, 30th International Symposium, Proceedings","first-page":"793","article-title":"Explicit inapproximability bounds for the shortest superstring problem","volume":"vol. 3618","author":"Vassilevska","year":"2005"}],"container-title":["Journal of Discrete Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S1570866716300065?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S1570866716300065?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2018,9,11]],"date-time":"2018-09-11T19:00:01Z","timestamp":1536692401000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S1570866716300065"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,3]]},"references-count":20,"alternative-id":["S1570866716300065"],"URL":"https:\/\/doi.org\/10.1016\/j.jda.2016.05.001","relation":{},"ISSN":["1570-8667"],"issn-type":[{"type":"print","value":"1570-8667"}],"subject":[],"published":{"date-parts":[[2016,3]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"A linear time algorithm for Shortest Cyclic Cover of Strings","name":"articletitle","label":"Article Title"},{"value":"Journal of Discrete Algorithms","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/j.jda.2016.05.001","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"article","name":"content_type","label":"Content Type"},{"value":"\u00a9 2016 The Author(s). Published by Elsevier B.V.","name":"copyright","label":"Copyright"}]}}