{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T16:40:49Z","timestamp":1725468049626},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540638766"},{"type":"electronic","value":"9783540696599"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1997]]},"DOI":"10.1007\/bfb0058021","type":"book-chapter","created":{"date-parts":[[2006,8,3]],"date-time":"2006-08-03T10:48:04Z","timestamp":1154602084000},"page":"37-53","source":"Crossref","is-referenced-by-count":4,"title":["Graph editing to bipartite interval graphs: Exact and asymptotic bounds"],"prefix":"10.1007","author":[{"given":"K.","family":"Cirino","sequence":"first","affiliation":[]},{"given":"S.","family":"Muthukrishnan","sequence":"additional","affiliation":[]},{"given":"N. S.","family":"Narayanaswamy","sequence":"additional","affiliation":[]},{"given":"H.","family":"Ramesh","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2006,7,13]]},"reference":[{"key":"4_CR1","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1016\/0095-8956(89)90003-8","volume":"46","author":"T. Andrae","year":"1989","unstructured":"T. Andrae and M. Aigner. The total interval number of a graph. J. Comb. Theory, Series B, 46, 7\u201321, 1989.","journal-title":"J. Comb. Theory, Series B"},{"issue":"2","key":"4_CR2","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1089\/cmb.1995.2.159","volume":"2","author":"F. Alizadeh","year":"1995","unstructured":"F. Alizadeh, R.M. Karp, D.K. Weisser, G. Zweig, Physical Mapping of Chromosomes Using Unique Probes, J. Comp. Bio., 2(2):153\u2013158, 1995.","journal-title":"J. Comp. Bio."},{"key":"4_CR3","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/0166-218X(89)90031-0","volume":"23","author":"S. Arnborg","year":"1989","unstructured":"S. Arnborg, A. Proskurowski, Linear Time Algorithms for NP-Hard Problems Restricted to Partial k-Trees, Discrete Applied Mathematics, 23:11\u201324, 1989.","journal-title":"Discrete Applied Mathematics"},{"key":"4_CR4","unstructured":"H. Bodlaender. A tourist guide through treewidth. Manuscript, 1995."},{"key":"4_CR5","unstructured":"H. Bodlaender, M. Fellows, M. Hallet, T. Wareham and T. Warnow. The hardness of problems on thin colored graphs. Manuscript, 1995."},{"key":"4_CR6","doi-asserted-by":"crossref","unstructured":"H. Bodlaender, and B. de Fluiter. Intervalizing k-colored graphs. Proc. ICALP, 1995. Also, see http:\/\/www.cs.ruu.nl\/~hansb\/mypapers2.html for the journal version.","DOI":"10.1007\/3-540-60084-1_65"},{"key":"4_CR7","doi-asserted-by":"crossref","unstructured":"H. Bodlaender, M. Fellows, and M. Hallet. Beyond the NP Completeness for problems of bounded width. Proc. STOC, 449\u2013458, 1994.","DOI":"10.1145\/195058.195229"},{"key":"4_CR8","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1016\/S0022-0000(76)80045-1","volume":"13","author":"K. Booth","year":"1976","unstructured":"K. Booth and G. Leuker. Testing for the consecutive ones property, interval graphs and graph planarity using PQ algorithms. J. Comput. Syst. Sciences, 13, 335\u2013379, 1976.","journal-title":"J. Comput. Syst. Sciences"},{"volume-title":"The Human Genome Project \u2014 Deciphering the Blueprint of Heredity","year":"1994","key":"4_CR9","unstructured":"N. G. Cooper(editor). The Human Genome Project \u2014 Deciphering the Blueprint of Heredity, University Science Books, Mill Valley, California, 1994."},{"key":"4_CR10","unstructured":"P. Cresenzi and V. Kann. The NP Completeness Compendium. See Section on Subgraphs and Supergraphs. http:\/\/www.nada.kth.se\/viggo\/problemlist\/compendium."},{"key":"4_CR11","doi-asserted-by":"crossref","unstructured":"M. Farach, S. Kannan and T. Warnow. A robust model for constructing evolutionary trees. Proc. STOC, 1994.","DOI":"10.1145\/167088.167132"},{"key":"4_CR12","doi-asserted-by":"crossref","unstructured":"M. Fellows, M. Hallet and T. Wareham. DNA Physical Mapping: three ways difficult. Proc. First ESA, 157\u2013168, 1993.","DOI":"10.1007\/3-540-57273-2_52"},{"issue":"1","key":"4_CR13","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1089\/cmb.1995.2.139","volume":"2","author":"P.W. Goldberg","year":"1995","unstructured":"P.W. Goldberg, M.C. Golumbic, H. Kaplan, R. Shamir, Four Strikes Against Physical Mapping of DNA, J. Comp. Bio., 2(1):139\u2013152, 1995.","journal-title":"J. Comp. Bio."},{"key":"4_CR14","first-page":"199","volume-title":"Computers and Intractability: A Guide to the Theory of N P-Completeness","author":"M.R. Garey","year":"1979","unstructured":"M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of N P-Completeness, p 199\u2013200. (Freeman, San Fransisco, CA, 1979)"},{"key":"4_CR15","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."},{"key":"4_CR16","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1006\/aama.1994.1009","volume":"15","author":"M. Golumbic","year":"1994","unstructured":"M. Golumbic, H. Kaplan and R. Shamir On the complexity of DNA physical mapping. Adv. Appl. Math., 15:251\u2013261, 1994.","journal-title":"Adv. Appl. Math."},{"key":"4_CR17","doi-asserted-by":"crossref","unstructured":"H. Kaplan and R. Shamir. Pathwidth, bandwidth and completion problems to proper interval graphs with small cliques. To appear in SIAM. J. Computing, 1996.","DOI":"10.1137\/S0097539793258143"},{"key":"4_CR18","unstructured":"H. Kaplan and R. Shamir. Physical mapping and interval sandwich problems: Bounded degrees help. Manuscript, 1996."},{"key":"4_CR19","unstructured":"H. Kaplan, R. Shamir and R. Tarjan. Tractability of parameterized completion problems on chordal and interval graphs: Minimum fill-in and physical mapping. Procs. of FOCS, 1994."},{"key":"4_CR20","doi-asserted-by":"crossref","unstructured":"R. Karp, Mapping the Genome: Some Combinatorial Problems Arising in Molecular Biology, 25th ACM STOC, 1993.","DOI":"10.1145\/167088.167170"},{"key":"4_CR21","doi-asserted-by":"crossref","unstructured":"P. Pevzner, M. Waterman. Open Combinatorial Problems in Computational Molecular Biology, Proceedings of the Third Israel Symposium on Theory of Computing and Systems, Jan 4\u20136, 1995, Tel Aviv, Israel.","DOI":"10.1109\/ISTCS.1995.377035"},{"key":"4_CR22","doi-asserted-by":"crossref","unstructured":"J. Rose. A graph-theoretic study of the numerical solution of sparse positive definite systems of linear equations. Reed Eds. Graph Theory and Computing, 183\u2013217, Academic Press, NY, 1972.","DOI":"10.1016\/B978-1-4832-3187-7.50018-0"},{"key":"4_CR23","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/S0092-8240(86)80006-4","volume":"48","author":"M. Waterman","year":"1986","unstructured":"M. Waterman, J. R. Griggs, Interval Graphs and Maps of DNA, Bull. of Math. Biol., 48:189\u2013195, 1986.","journal-title":"Bull. of Math. Biol."},{"key":"4_CR24","doi-asserted-by":"crossref","unstructured":"M. Yannakakis. Computing the minimum fill-in is NP-Complete. SIAM J. ALg. Disc. Methods, 2, 1981.","DOI":"10.1137\/0602010"},{"key":"4_CR25","unstructured":"C. Wang. A subgraph problem from restriction maps of DNA chain. Journal of Computational Biology, 1995."}],"container-title":["Lecture Notes in Computer Science","Foundations of Software Technology and Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0058021","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,20]],"date-time":"2019-04-20T14:03:23Z","timestamp":1555769003000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0058021"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997]]},"ISBN":["9783540638766","9783540696599"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/bfb0058021","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1997]]}}}