{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:16:58Z","timestamp":1759637818253},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2013,10,4]],"date-time":"2013-10-04T00:00:00Z","timestamp":1380844800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2014,7]]},"DOI":"10.1007\/s10878-013-9663-3","type":"journal-article","created":{"date-parts":[[2013,10,3]],"date-time":"2013-10-03T05:21:12Z","timestamp":1380777672000},"page":"25-37","source":"Crossref","is-referenced-by-count":5,"title":["Recognition of overlap graphs"],"prefix":"10.1007","volume":"28","author":[{"given":"Theodoros P.","family":"Gevezes","sequence":"first","affiliation":[]},{"given":"Leonidas S.","family":"Pitsoulis","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2013,10,4]]},"reference":[{"key":"9663_CR1","doi-asserted-by":"crossref","first-page":"669","DOI":"10.1016\/0024-3795(89)90487-4","volume":"114115","author":"N Alon","year":"1989","unstructured":"Alon N, Cosares S, Hochbaum DS, Shamir R (1989) An algorithm for the detection and construction of monge sequences. Linear Algebra Appl 114115:669\u2013680 ISSN: 0024-3795. Special issue dedicated to Alan J. Hoffman","journal-title":"Linear Algebra Appl"},{"issue":"3","key":"9663_CR2","doi-asserted-by":"crossref","first-page":"487","DOI":"10.1137\/0606048","volume":"6","author":"ER Barnes","year":"1985","unstructured":"Barnes ER, Hoffman AJ (1985) On transportation problems with upper bounds on leading rectangles. SIAM J Algebr Discret Methods 6(3):487\u2013496","journal-title":"SIAM J Algebr Discret Methods"},{"key":"9663_CR3","doi-asserted-by":"crossref","first-page":"630","DOI":"10.1145\/179812.179818","volume":"41","author":"A Blum","year":"1994","unstructured":"Blum A, Jiang T, Li M, Tromp J, Yannakakis M (1994) Linear approximation of shortest superstrings. J ACM 41:630\u2013647 ISSN: 0004-5411","journal-title":"J ACM"},{"key":"9663_CR4","unstructured":"Braga MDV, Meidanis J (2002) An algorithm that builds a set of strings given its overlap graph. In Proceedings of the 5th Latin American symposium on theoretical informatics, LATIN \u201902, pp 52\u201363, London, UK, Springer. ISBN: 3-540-43400-3"},{"key":"9663_CR5","doi-asserted-by":"crossref","first-page":"74","DOI":"10.1006\/jagm.1996.0823","volume":"23","author":"A Czumaj","year":"1997","unstructured":"Czumaj A, Ga\u0327sieniec L, Piotr\u00f3w M, Rytter W (1997) Sequential and parallel approximation of shortest superstrings. J Algorithms 23:74\u2013100 ISSN: 0196-6774","journal-title":"J Algorithms"},{"issue":"1","key":"9663_CR6","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1016\/0022-0000(80)90004-5","volume":"20","author":"J Gallant","year":"1980","unstructured":"Gallant J, Maier D, Storer JA (1980) On finding minimal length superstrings. J Comput Syst Sci 20(1):50\u201358 ISSN: 0022-0000","journal-title":"J Comput Syst Sci"},{"key":"9663_CR7","unstructured":"Gevezes T, Pitsoulis L (2013) A greedy randomized adaptive search procedure with path relinking for the shortest superstring problem. J Comb Optim ISSN: 1382-6905"},{"issue":"2","key":"9663_CR8","doi-asserted-by":"crossref","first-page":"529","DOI":"10.1093\/nar\/7.2.529","volume":"7","author":"TR Gingeras","year":"1979","unstructured":"Gingeras TR, Milazzo PJ, Sciaky D, Roberts RJ (1979) Computer programs for the assembly of DNA sequences. Nucl Acids Res 7(2):529\u2013543","journal-title":"Nucl Acids Res"},{"issue":"5","key":"9663_CR9","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1016\/0020-0190(94)00097-2","volume":"51","author":"D Gusfield","year":"1994","unstructured":"Gusfield D (1994) Faster implementation of a shortest superstring approximation. Inf Proces Lett 51(5):271\u2013274 ISSN: 0020-0190","journal-title":"Inf Proces Lett"},{"key":"9663_CR10","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1016\/0020-0190(92)90176-V","volume":"41","author":"D Gusfield","year":"1992","unstructured":"Gusfield D, Landau GM, Schieber B (1992) An efficient algorithm for the all pairs suffix\u2013prefix problem. Inf Process Lett 41:181\u2013185 ISSN: 0020-0190","journal-title":"Inf Process Lett"},{"key":"9663_CR11","first-page":"153","volume":"73","author":"L Ilie","year":"2006","unstructured":"Ilie L, Popescu C (2006) The shortest common superstring problem and viral genome compression. Fundam Inf 73:153\u2013164 ISSN: 0169-2968","journal-title":"Fundam Inf"},{"key":"9663_CR12","doi-asserted-by":"crossref","unstructured":"Ilie L, Tinta L, Popescu C, Hill KA (2006) Viral genome compression. In: Mao C, Yokomori T (eds) DNA computing, vol 4287 of lecture notes in computer science, pp Springer, Berlin\/Heidelberg, pp 111\u2013126","DOI":"10.1007\/11925903_9"},{"issue":"4","key":"9663_CR13","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1002\/net.3230090406","volume":"9","author":"TA Jenkyns","year":"1979","unstructured":"Jenkyns TA (1979) The greedy travelling salesman\u2019s problem. Networks 9(4):363\u2013373 ISSN: 1097-0037","journal-title":"Networks"},{"issue":"2","key":"9663_CR14","doi-asserted-by":"crossref","first-page":"473","DOI":"10.1016\/0304-3975(94)90249-6","volume":"134","author":"T Jiang","year":"1994","unstructured":"Jiang T, Li M (1994) Approximating shortest superstrings with constraints. Theor Comput Sci 134(2):473\u2013491 ISSN: 0304-3975","journal-title":"Theor Comput Sci"},{"issue":"1\u20132","key":"9663_CR15","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1016\/S0304-3975(97)00133-3","volume":"191","author":"M Middendorf","year":"1998","unstructured":"Middendorf M (1998) Shortest common superstrings and scheduling with coordinated starting times. Theor Comput Sci 191(1\u20132):205\u2013214 ISSN: 0304-3975","journal-title":"Theor Comput Sci"},{"key":"9663_CR16","doi-asserted-by":"crossref","first-page":"720","DOI":"10.1145\/321420.321431","volume":"14","author":"MB Shapiro","year":"1967","unstructured":"Shapiro MB (1967) An algorithm for reconstructing protein and RNA sequences. J ACM 14:720\u2013731 ISSN: 0004-5411","journal-title":"J ACM"},{"issue":"15","key":"9663_CR17","doi-asserted-by":"crossref","first-page":"4731","DOI":"10.1093\/nar\/10.15.4731","volume":"10","author":"Roger Staden","year":"1982","unstructured":"Staden Roger (1982) Automation of the computer handling of gel reading data produced by the shotgun method of DNA sequencing. Nucl Acids Res 10(15):4731\u20134751","journal-title":"Nucl Acids Res"},{"key":"9663_CR18","doi-asserted-by":"crossref","first-page":"928","DOI":"10.1145\/322344.322346","volume":"29","author":"JA Storer","year":"1982","unstructured":"Storer JA, Szymanski TG (1982) Data compression via textual substitution. J ACM 29:928\u2013951 ISSN 0004-5411","journal-title":"J ACM"},{"issue":"1","key":"9663_CR19","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1016\/0304-3975(88)90167-3","volume":"57","author":"J Tarhio","year":"1988","unstructured":"Tarhio J, Ukkonen E (1988) A greedy approximation algorithm for constructing shortest common superstrings. Theor Comput Sci 57(1):131\u2013145 ISSN: 0304\u20133975","journal-title":"Theor Comput Sci"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-013-9663-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-013-9663-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-013-9663-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,7,28]],"date-time":"2019-07-28T17:13:24Z","timestamp":1564334004000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-013-9663-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,10,4]]},"references-count":19,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2014,7]]}},"alternative-id":["9663"],"URL":"https:\/\/doi.org\/10.1007\/s10878-013-9663-3","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,10,4]]}}}