{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:14:21Z","timestamp":1759637661922},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540003311"},{"type":"electronic","value":"9783540363798"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-36379-3_2","type":"book-chapter","created":{"date-parts":[[2010,3,29]],"date-time":"2010-03-29T17:12:05Z","timestamp":1269882725000},"page":"13-24","source":"Crossref","is-referenced-by-count":5,"title":["DNA Sequencing, Eulerian Graphs, and the Exact Perfect Matching Problem"],"prefix":"10.1007","author":[{"given":"Jacek","family":"B\u0142a\u017cewicz","sequence":"first","affiliation":[]},{"given":"Piotr","family":"Formanowicz","sequence":"additional","affiliation":[]},{"given":"Marta","family":"Kasprzak","sequence":"additional","affiliation":[]},{"given":"Petra","family":"Schuurman","sequence":"additional","affiliation":[]},{"given":"Gerhard J.","family":"Woeginger","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2003,2,28]]},"reference":[{"key":"2_CR1","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1016\/S0022-5193(88)80246-7","volume":"135","author":"W. Bains","year":"1988","unstructured":"W. Bains and G.C. Smith [1988]. A novel method for nucleic acid sequence determination. Journal of Theoretical Biology 135, 303\u2013307.","journal-title":"Journal of Theoretical Biology"},{"key":"2_CR2","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1016\/0166-218X(87)90067-9","volume":"16","author":"F. Barahona","year":"1987","unstructured":"F. Barahona and W.R. Pulleyblank [1987]. Exact arborescences, matchings, and cycles. Discrete Applied Mathematics 16, 91\u201399.","journal-title":"Discrete Applied Mathematics"},{"key":"2_CR3","unstructured":"C. Berge [1973]. Graphs and Hypergraphs. North Holland."},{"key":"2_CR4","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1089\/cmb.1999.6.113","volume":"6","author":"J. B\u0142a\u017cewicz","year":"1999","unstructured":"J. B\u0142a\u017cewicz, P. Formanowicz, M. Kasprzak, W.T. Markiewicz, and J. Weglarz [1999]. DNA sequencing with positive and negative errors. Journal of Computational Biology 6, 113\u2013123.","journal-title":"Journal of Computational Biology"},{"key":"2_CR5","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0166-218X(99)00109-2","volume":"98","author":"J. B\u0142a\u017cewicz","year":"1999","unstructured":"J. B\u0142a\u017cewicz, A. Hertz, D. Kobler, and D. de Werra [1999]. On some properties of DNA graphs. Discrete Applied Mathematics 98, 1\u201319.","journal-title":"Discrete Applied Mathematics"},{"key":"2_CR6","unstructured":"J. B\u0142a\u017cewicz and M. Kasprzak [2001]. Complexity of DNA sequencing by hybridization. To appear in Theoretical Computer Science."},{"key":"2_CR7","unstructured":"N.G. de Bruijn [1946]. A combinatorial problem. Koninklijke Nederlandse Akademie van Wetenschappen te Amsterdam. Proceedings 49, 758\u2013764."},{"key":"2_CR8","doi-asserted-by":"crossref","first-page":"399","DOI":"10.4064\/aa-21-1-399-408","volume":"21","author":"P. Erdos","year":"1972","unstructured":"P. Erdos and R.L. Graham [1972]. On a linear diophantine problem of Frobenius. Acta Arithmetica 21, 399\u2013408.","journal-title":"Acta Arithmetica"},{"key":"2_CR9","doi-asserted-by":"crossref","unstructured":"A.V. Karzanov [1987]. Maximum matching of given weight in complete and complete bipartite graphs. Cybernetics 23, 8\u201313; translation from Kibernetika 1, 1987, 7-11.","DOI":"10.1007\/BF01068796"},{"key":"2_CR10","unstructured":"M. Leclerc [1986]. Polynomial time algorithms for exact matching problems. Master\u2019s thesis, University of Waterloo, Waterloo."},{"key":"2_CR11","doi-asserted-by":"crossref","unstructured":"M. Leclerc [1988\/89]. Optimizing over a slice of the bipartite matching polytope. Discrete Mathematics 73, 159\u2013162.","DOI":"10.1016\/0012-365X(88)90143-4"},{"key":"2_CR12","unstructured":"S. Martello and P. Toth [1990]. Knapsack problems: Algorithms and computer implementations. John Wiley & Sons."},{"key":"2_CR13","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1007\/BF02579206","volume":"7","author":"K. Mulmuley","year":"1987","unstructured":"K. Mulmuley, U. Vazirani, and V.V. Vazirani [1987]. Matching is as easy as matrix inversion. Combinatorica 7, 105\u2013113.","journal-title":"Combinatorica"},{"key":"2_CR14","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1145\/322307.322309","volume":"29","author":"C.H. Papadimitriou","year":"1982","unstructured":"C.H. Papadimitriou and M. Yannakakis [1982]. The complexity of restricted spanning tree problems. Journal of the ACM 29, 285\u2013309.","journal-title":"Journal of the ACM"},{"key":"2_CR15","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1080\/07391102.1989.10507752","volume":"7","author":"P.A. Pevzner","year":"1989","unstructured":"P.A. Pevzner [1989]. l-tuple DNA sequencing: Computer analysis. Journal of Biomolecular Structure and Dynamics 7, 63\u201373.","journal-title":"Journal of Biomolecular Structure and Dynamics"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-36379-3_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,27]],"date-time":"2019-05-27T14:45:09Z","timestamp":1558968309000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-36379-3_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540003311","9783540363798"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/3-540-36379-3_2","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2002]]}}}