{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T00:37:55Z","timestamp":1725496675829},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540677871"},{"type":"electronic","value":"9783540449683"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-44968-x_38","type":"book-chapter","created":{"date-parts":[[2007,11,29]],"date-time":"2007-11-29T09:37:43Z","timestamp":1196329063000},"page":"383-395","source":"Crossref","is-referenced-by-count":3,"title":["The Complexity of Physical Mapping with Strict Chimerism"],"prefix":"10.1007","author":[{"given":"Stephan","family":"Weis","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"R\u00fcdiger","family":"Reischuk","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2000,7,21]]},"reference":[{"key":"38_CR1","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1007\/BF01188581","volume":"13","author":"F. Alizadeh","year":"1995","unstructured":"F. Alizadeh, R. Karp, L. Newberg, D. Weisser, Physical mapping of chromosomes: a combinatorial problem in molecular biology, Algorithmica 13, 52\u201376, 1995.","journal-title":"Algorithmica"},{"key":"38_CR2","unstructured":"F. Alizadeh, R. Karp, D. Weisser, G. Zweig, Physical mapping of chromosomes using unique probes, Proc. 5th Annual ACM-SIAM Symposium on Discrete Algorithms SODA\u201994, 489\u2013500, 1994."},{"key":"38_CR3","doi-asserted-by":"crossref","unstructured":"J. Atkins, M. Middendorf, On physical mapping and the consecutive ones property for sparse matrices, DAMATH: Discrete Applied Mathematics and Combinatorial Operations Research and Computer Science 71, 1996.","DOI":"10.1016\/S0166-218X(96)00055-8"},{"key":"38_CR4","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/S0022-0000(76)80045-1","volume":"13","author":"K. Booth","year":"1976","unstructured":"K. Booth, G. Lueker, Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms, J. Computer and System Sciences 13, 335\u2013379, 1976.","journal-title":"J. Computer and System Sciences"},{"key":"38_CR5","doi-asserted-by":"crossref","first-page":"835","DOI":"10.2140\/pjm.1965.15.835","volume":"15","author":"D. Fulkerson","year":"1965","unstructured":"D. Fulkerson, O. Gross, Incidence matrices and interval graphs, Pacific Journal of Mathematics 15, 835\u2013856, 1965.","journal-title":"Pacific Journal of Mathematics"},{"key":"38_CR6","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1089\/cmb.1995.2.139","volume":"2","author":"P. Goldberg","year":"1995","unstructured":"P. Goldberg, M. Golumbic, H. Kaplan, R. Shamir, Four strikes against physical mapping of DNA, J. Computational Biology 2, 139\u2013152, 1995.","journal-title":"J. Computational Biology"},{"key":"38_CR7","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1016\/0097-8485(94)85015-1","volume":"18","author":"D. Greenberg","year":"1994","unstructured":"D. Greenberg, S. Istrail, The chimeric mapping problem: Algorithmic strategies and performance evaluation on synthetic genomic data, Computers and Chemistry 18, 207\u2013220, 1994.","journal-title":"Computers and Chemistry"},{"key":"38_CR8","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1089\/cmb.1995.2.219","volume":"2","author":"D. Greenberg","year":"1995","unstructured":"D. Greenberg, S. Istrail, Physical Mapping by STS Hybridization: Algorithmic Strategies and the challenge of Software Evaluation, J. Comp. Biology 2, 219\u2013273, 1995.","journal-title":"J. Comp. Biology"},{"key":"38_CR9","unstructured":"M. Garey, D. Johnson, Computers and Intractability: A Guide to NP-Completeness, Freeman, 1979."},{"key":"38_CR10","doi-asserted-by":"publisher","first-page":"704","DOI":"10.1137\/0205049","volume":"5","author":"M. Garey","year":"1976","unstructured":"M. Garey, D. Johnson, R. Tarjan, The planar Hamiltonian circuit problem is NP-complete, SIAM J. Computing 5, 704\u2013714, 1976.","journal-title":"SIAM J. Computing"},{"key":"38_CR11","unstructured":"To Know Ourselves. Human Genome Program, U.S. Department of Energy, 1996."},{"key":"38_CR12","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"459","DOI":"10.1007\/3-540-56279-6_98","volume-title":"Proc. 3rd Int. Symposium on Algorithms and Computation ISAAC\u201992","author":"W. Hsu","year":"1992","unstructured":"W. Hsu. A simple test for the consecutive ones property, Proc. 3rd Int. Symposium on Algorithms and Computation ISAAC\u201992, LNCS650, 459\u2013468, 1992."},{"key":"38_CR13","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"242","DOI":"10.1007\/BFb0045091","volume-title":"Proc. 3rd Int. Conf. Computing and Combinatorics, COCOON\u201997","author":"W. Hsu","year":"1997","unstructured":"W. Hsu, On physical mapping algorithms: an error tolerant test for the consecutive ones property, Proc. 3rd Int. Conf. Computing and Combinatorics, COCOON\u201997, LNCS 1267, 242\u2013250, 1997."},{"key":"38_CR14","doi-asserted-by":"crossref","unstructured":"H. Kaplan, R. Shamir, R. Tarjan. Tractability of parameterized completion problems on chordal and interval graphs: Minimum fill-in and physical mapping, Proc. 35th Symp. on Foundations of Computer Science FOCS\u201994, 780\u2013793, 1994.","DOI":"10.1109\/SFCS.1994.365715"},{"key":"38_CR15","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1137\/0218005","volume":"18","author":"N. Korte","year":"1989","unstructured":"N. Korte, R. M\u00f6hring. An incremental linear-time algorithm for recognizing interval graphs, SIAM J. Computing 18, 68\u201381, 1989.","journal-title":"SIAM J. Computing"},{"key":"38_CR16","unstructured":"S. Weis, Das Entscheidungsproblem Physikalische Kartierung mit starkchimerischen Fehlern, Technical Report A-99-05, Med. Uni. L\u00fcbeck, Institut f\u00fcr Theoretische Informatik, 1999."},{"key":"38_CR17","unstructured":"S. Weis, Zur algorithmischen Komplexit\u00e4t des Optimierungsproblems Physikalische Kartierung mit starkchimerischen Fehlern, Technical Report A-99-06, Med. Uni. L\u00fcbeck, Institut f\u00fcr Theoretische Informatik, 1999."}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44968-X_38","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,5]],"date-time":"2019-05-05T08:17:08Z","timestamp":1557044228000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44968-X_38"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540677871","9783540449683"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/3-540-44968-x_38","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2000]]}}}