{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T23:47:52Z","timestamp":1725493672774},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540405344"},{"type":"electronic","value":"9783540450719"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/3-540-45071-8_20","type":"book-chapter","created":{"date-parts":[[2007,10,27]],"date-time":"2007-10-27T08:04:43Z","timestamp":1193472283000},"page":"182-191","source":"Crossref","is-referenced-by-count":0,"title":["Finding Hidden Independent Sets in Interval Graphs"],"prefix":"10.1007","author":[{"given":"Therese","family":"Biedl","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bro\u0148a","family":"Brejov\u00e1","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Erik D.","family":"Demaine","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ang\u00e8le M.","family":"Hamel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alejandro","family":"L\u00f3pez-Ortiz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tom\u00e1\u0161","family":"Vina\u0159","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2003,6,24]]},"reference":[{"key":"20_CR1","unstructured":"Battleships variations. Mountain Vista Software. Web page. See http:\/\/www.mountainvistasoft.com\/variations.htm"},{"key":"20_CR2","doi-asserted-by":"crossref","unstructured":"R. Beigel, N. Alon, M. S. Apydin, and L. Fortnow. An optimal procedure for gap closing in whole genome shotgun sequencing. In 5th Annual International Conference on Computational Molecular Biology (RECOMB), pages 22\u201330, 2001.","DOI":"10.1145\/369133.369152"},{"issue":"2","key":"20_CR3","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/0304-3975(92)90254-D","volume":"106","author":"H. L. Bodlaender","year":"1992","unstructured":"H. L. Bodlaender and D. Kratsch. The complexity of coloring games on perfect graphs. Theoretical Computer Science, 106(2):309\u2013326, 1992.","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"20_CR4","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1006\/jmbi.1997.0951","volume":"268","author":"C. Burge","year":"1997","unstructured":"C. Burge and S. Karlin. Prediction of complete gene structures in human genomic DNA. Journal of Molecular Biology, 268(1):78\u201394, 1997.","journal-title":"Journal of Molecular Biology"},{"issue":"1\u20132","key":"20_CR5","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1006\/geno.2001.6620","volume":"77","author":"M. Das","year":"2001","unstructured":"M. Das, C. B. Burge, E. Park, J. Colinas, and J. Pelletier. Assessment of the total number of human transcription units. Genomics, 77(1\u20132):71\u201378, 2001.","journal-title":"Genomics"},{"key":"20_CR6","unstructured":"E. D. Demaine, A. L\u00f3pez-Ortiz, and J. I. Munro. Adaptive set intersections, unions, and differences. In 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 743\u2013752, 2000."},{"issue":"6761","key":"20_CR7","doi-asserted-by":"publisher","first-page":"489","DOI":"10.1038\/990031","volume":"402","author":"I. Dunham","year":"1999","unstructured":"I. Dunham et al. The DNA sequence of human chromosome 22. Nature, 402(6761):489\u2013495, 1999.","journal-title":"Nature"},{"key":"20_CR8","doi-asserted-by":"publisher","first-page":"298","DOI":"10.1016\/0097-3165(73)90005-8","volume":"14","author":"P. Erd\u0151s","year":"1973","unstructured":"P. Erd\u0151s and J. L. Selfridge. On a combinatorial game. Journal of Combinatorial Theory-Series A, 14:298\u2013301, 1973.","journal-title":"Journal of Combinatorial Theory-Series A"},{"key":"20_CR9","doi-asserted-by":"publisher","first-page":"507","DOI":"10.1137\/0204043","volume":"4","author":"S. Even","year":"1975","unstructured":"S. Even and R. E. Tarjan. Network flow and testing graph connectivity. SIAM Journal on Computing, 4:507\u2013518, 1975.","journal-title":"SIAM Journal on Computing"},{"key":"20_CR10","doi-asserted-by":"crossref","unstructured":"R. Fagin, A. Lotem, and M. Naor. Optimal aggregation algorithms for middleware. In 20th ACM Symposium on Principle of Database Systems (PODS), pages 102\u2013113, 2001.","DOI":"10.1145\/375551.375567"},{"key":"20_CR11","volume-title":"Algorithmic graph theory and perfect graphs","author":"M. C. Golumbic","year":"1980","unstructured":"M. C. Golumbic. Algorithmic graph theory and perfect graphs. Academic Press, New York, 1980."},{"issue":"2","key":"20_CR12","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/0304-3975(86)90146-5","volume":"47","author":"L. M. Kirousis","year":"1986","unstructured":"L. M. Kirousis and C. H. Papadimitriou. Searching and pebbling. Theoretical Computer Science, 47(2):205\u2013218, 1986.","journal-title":"Theoretical Computer Science"},{"key":"20_CR13","unstructured":"R. M. McConnell and J. P. Spinrad. Construction of probe interval models. In 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 866\u2013875, 2002."},{"issue":"11","key":"20_CR14","doi-asserted-by":"publisher","first-page":"887","DOI":"10.1093\/bioinformatics\/15.11.887","volume":"15","author":"N. Pavy","year":"1999","unstructured":"N. Pavy, S. Rombauts, P. Dehais, C. Mathe, D. V. Ramana, P. Leroy, and P. Rouze. Evaluation of gene prediction software using a genomic data set: application to Arabidopsis thaliana sequences. Bioinformatics, 15(11):887\u2013889, 1999.","journal-title":"Bioinformatics"},{"key":"20_CR15","doi-asserted-by":"crossref","unstructured":"P. A. Pevzner. Computational molecular biology: an algorithmic approach. MIT Press, 2000.","DOI":"10.7551\/mitpress\/2022.001.0001"},{"issue":"4","key":"20_CR16","doi-asserted-by":"publisher","first-page":"516","DOI":"10.1101\/gr.10.4.516","volume":"10","author":"A. A. Salamov","year":"2000","unstructured":"A. A. Salamov and V. V. Solovyev. Ab initio gene finding in Drosophila genomic DNA. Genome Research, 10(4):516\u2013522, 2000.","journal-title":"Genome Research"},{"issue":"4768","key":"20_CR17","doi-asserted-by":"publisher","first-page":"1076","DOI":"10.1126\/science.3461561","volume":"233","author":"S. J. Scharf","year":"1986","unstructured":"S. J. Scharf, G. T. Horn, and H. A. Erlich. Direct cloning and sequence analysis of enzymatically amplified genomic sequences. Science, 233(4768):1076\u20131078, 1986.","journal-title":"Science"},{"issue":"5235","key":"20_CR18","doi-asserted-by":"publisher","first-page":"467","DOI":"10.1126\/science.270.5235.467","volume":"270","author":"M. Schena","year":"1995","unstructured":"M. Schena, D. Shalon, R. W. Davis, and P. O. Brown. Quantitative monitoring of gene expression patterns with a complementary DNA microarray. Science, 270(5235):467\u2013470, 1995.","journal-title":"Science"},{"issue":"6822","key":"20_CR19","doi-asserted-by":"publisher","first-page":"922","DOI":"10.1038\/35057141","volume":"409","author":"D. D. Shoemaker","year":"2001","unstructured":"D. D. Shoemaker, E. E. Schadt, et al. Experimental annotation of the human genome using microarray technology. Nature, 409(6822):922\u2013927, 2001.","journal-title":"Nature"},{"issue":"2","key":"20_CR20","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1006\/geno.1997.5072","volume":"47","author":"G. Xu","year":"1998","unstructured":"G. Xu, S. H. Sze, C. P. Liu, P. A. Pevzner, and N. Arnheim. Gene hunting without sequencing genomic clones: finding exon boundaries in cDNAs. Genomics, 47(2):171\u2013179, 1998.","journal-title":"Genomics"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45071-8_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,4]],"date-time":"2019-05-04T02:09:15Z","timestamp":1556935755000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45071-8_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540405344","9783540450719"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/3-540-45071-8_20","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2003]]}}}