{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T12:08:35Z","timestamp":1759666115308},"reference-count":16,"publisher":"Elsevier BV","issue":"1-3","license":[{"start":{"date-parts":[[1996,12,1]],"date-time":"1996-12-01T00:00:00Z","timestamp":849398400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":6072,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Applied Mathematics"],"published-print":{"date-parts":[[1996,12]]},"DOI":"10.1016\/s0166-218x(96)00055-8","type":"journal-article","created":{"date-parts":[[2003,5,12]],"date-time":"2003-05-12T23:10:20Z","timestamp":1052781020000},"page":"23-40","source":"Crossref","is-referenced-by-count":15,"title":["On Physical Mapping and the consecutive ones property for sparse matrices"],"prefix":"10.1016","volume":"71","author":[{"given":"Jonathan E.","family":"Atkins","sequence":"first","affiliation":[]},{"given":"Martin","family":"Middendorf","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/S0166-218X(96)00055-8_BIB1","doi-asserted-by":"crossref","first-page":"52","DOI":"10.1007\/BF01188581","article-title":"Physical mapping of chromosomes: a combinatorial problem in molecular biology","volume":"13","author":"Alizadeh","year":"1995","journal-title":"Algorithmica"},{"key":"10.1016\/S0166-218X(96)00055-8_BIB2","unstructured":"J.E. Atkins, E.G. Boman and B. Hendrickson, A spectral algorithm for seriation and linear ordering problems, submitted for publication."},{"key":"10.1016\/S0166-218X(96)00055-8_BIB3","unstructured":"H.L. Bodlaender, M.R. Fellows and M.T. Hallet, The parameterized complexity of DNA mapping, perfect phylogeny and other problems of \u201cbounded width\u201d, manuscript."},{"key":"10.1016\/S0166-218X(96)00055-8_BIB4","first-page":"335","article-title":"Testing for the consecutive ones property interval graphs, and graph planarity using PQ-tree algorithms","volume":"13","author":"Booth","year":"1976","journal-title":"JCSS"},{"key":"10.1016\/S0166-218X(96)00055-8_BIB5","series-title":"Graph Algorithms","author":"Even","year":"1979"},{"key":"10.1016\/S0166-218X(96)00055-8_BIB6","series-title":"Proceedings of the 1st European Symp. on Algorithms (ESA '93)","first-page":"157","article-title":"DNA physical mapping: three ways difficult","volume":"Vol. 726","author":"Fellows","year":"1993"},{"key":"10.1016\/S0166-218X(96)00055-8_BIB7","series-title":"Proceedings of the 12th Symp. on Theoret. Aspects of Comput. Sci. (STACS '95)","first-page":"279","article-title":"Interval routing schemes","volume":"Vol. 900","author":"Flammini","year":"1995"},{"key":"10.1016\/S0166-218X(96)00055-8_BIB8","doi-asserted-by":"crossref","first-page":"835","DOI":"10.2140\/pjm.1965.15.835","article-title":"Incidence matrices and interval graphs","volume":"15","author":"Fulkerson","year":"1965","journal-title":"Pacific J. Math."},{"key":"10.1016\/S0166-218X(96)00055-8_BIB9","doi-asserted-by":"crossref","unstructured":"P.W. Goldberg, M.C. Golumbic, H. Kaplan and R. Shamir, Four strikes against physical mapping of DNA, J. Comput. Biol., to appear.","DOI":"10.1089\/cmb.1995.2.139"},{"key":"10.1016\/S0166-218X(96)00055-8_BIB10","doi-asserted-by":"crossref","unstructured":"D.S. Greenberg and S. Istrail, Physical mapping by STS hybridization: algorithmic strategies and the challenge of software evaluation, J. Comput. Biol., to appear.","DOI":"10.1089\/cmb.1995.2.219"},{"key":"10.1016\/S0166-218X(96)00055-8_BIB11","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1006\/aama.1994.1009","article-title":"On the complexity of DNA physical mapping","volume":"15","author":"Golumbic","year":"1994","journal-title":"Adv. Appl. Math."},{"key":"10.1016\/S0166-218X(96)00055-8_BIB12","series-title":"Computers and Intractability","author":"Garey","year":"1979"},{"key":"10.1016\/S0166-218X(96)00055-8_BIB13","unstructured":"S. Istrail, personal communication (1994)."},{"key":"10.1016\/S0166-218X(96)00055-8_BIB14","doi-asserted-by":"crossref","DOI":"10.1137\/S0097539793258143","article-title":"Pathwidth, bandwidth and completion problems to proper interval graphs with small cliques","author":"Kaplan","year":"1993"},{"key":"10.1016\/S0166-218X(96)00055-8_BIB15","series-title":"Proceedings of the FOCS'94","first-page":"780","article-title":"Tractability of parameterized completion problems on chordal and interval graphs: minimum fill-in and physical mapping","author":"Kaplan","year":"1994"},{"key":"10.1016\/S0166-218X(96)00055-8_BIB16","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1137\/0206004","article-title":"Polynomial complete consecutive information retrieval problems","volume":"6","author":"Kou","year":"1977","journal-title":"SIAM J. Comput."}],"container-title":["Discrete Applied Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0166218X96000558?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0166218X96000558?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,4,24]],"date-time":"2019-04-24T18:27:56Z","timestamp":1556130476000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0166218X96000558"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996,12]]},"references-count":16,"journal-issue":{"issue":"1-3","published-print":{"date-parts":[[1996,12]]}},"alternative-id":["S0166218X96000558"],"URL":"https:\/\/doi.org\/10.1016\/s0166-218x(96)00055-8","relation":{},"ISSN":["0166-218X"],"issn-type":[{"value":"0166-218X","type":"print"}],"subject":[],"published":{"date-parts":[[1996,12]]}}}