{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T11:57:22Z","timestamp":1725537442940},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642041273"},{"type":"electronic","value":"9783642041280"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-04128-0_32","type":"book-chapter","created":{"date-parts":[[2009,9,14]],"date-time":"2009-09-14T14:16:36Z","timestamp":1252937796000},"page":"349-360","source":"Crossref","is-referenced-by-count":2,"title":["Linear-Time Recognition of Probe Interval Graphs"],"prefix":"10.1007","author":[{"given":"Ross M.","family":"McConnell","sequence":"first","affiliation":[]},{"given":"Yahav","family":"Nussbaum","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"32_CR1","doi-asserted-by":"publisher","first-page":"1607","DOI":"10.1073\/pnas.45.11.1607","volume":"45","author":"S. Benzer","year":"1959","unstructured":"Benzer, S.: On the topology of the genetic fine structure. Proc. Nat. Acad. Sci. U.S.A.\u00a045, 1607\u20131620 (1959)","journal-title":"Proc. Nat. Acad. Sci. U.S.A."},{"key":"32_CR2","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/S0022-0000(76)80045-1","volume":"13","author":"K.S. Booth","year":"1976","unstructured":"Booth, K.S., Lueker, G.S.: Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. J. Comput. Syst. Sci.\u00a013, 335\u2013379 (1976)","journal-title":"J. Comput. Syst. Sci."},{"key":"32_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"368","DOI":"10.1007\/978-3-540-72870-2_35","volume-title":"Algorithmic Aspects in Information and Management","author":"D.B. Chandler","year":"2007","unstructured":"Chandler, D.B., Guo, J., Kloks, T., Niedermeier, R.: Probe matrix problems: Totally balanced matrices. In: Kao, M.-Y., Li, X.-Y. (eds.) AAIM 2007. LNCS, vol.\u00a04508, pp. 368\u2013377. Springer, Heidelberg (2007)"},{"key":"32_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"521","DOI":"10.1007\/978-3-540-31856-9_43","volume-title":"STACS 2005","author":"G.J. Chang","year":"2005","unstructured":"Chang, G.J., Kloks, T., Liu, J., Peng, S.-L.: The PIGSs full monty - a floor show of minimal separators. In: Diekert, V., Durand, B. (eds.) STACS 2005. LNCS, vol.\u00a03404, pp. 521\u2013532. Springer, Heidelberg (2005)"},{"key":"32_CR5","volume-title":"Introduction to Algorithms","author":"T.H. Cormen","year":"2001","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms. McGraw Hill, Boston (2001)"},{"key":"32_CR6","doi-asserted-by":"publisher","first-page":"835","DOI":"10.2140\/pjm.1965.15.835","volume":"15","author":"D.R. Fulkerson","year":"1965","unstructured":"Fulkerson, D.R., Gross, O.: Incidence matrices and interval graphs. Pacific J. Math.\u00a015, 835\u2013855 (1965)","journal-title":"Pacific J. Math."},{"key":"32_CR7","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"M.C. Golumbic","year":"1980","unstructured":"Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York (1980)"},{"key":"32_CR8","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1016\/S0024-3795(97)10075-1","volume":"277","author":"M.C. Golumbic","year":"1998","unstructured":"Golumbic, M.C.: Matrix sandwich problems. Linear Algebra and Applications\u00a0277, 239\u2013251 (1998)","journal-title":"Linear Algebra and Applications"},{"key":"32_CR9","doi-asserted-by":"crossref","unstructured":"Golumbic, M.C., Trenk, A.N.: Tolerance Graphs. Cambridge studies in advanced mathematics 89, New York (2004)","DOI":"10.1017\/CBO9780511542985"},{"key":"32_CR10","first-page":"477","volume-title":"SODA 2001","author":"J.L. Johnson","year":"2001","unstructured":"Johnson, J.L., Spinrad, J.P.: A polynomial time recognition algorithm for probe interval graphs. In: SODA 2001, pp. 477\u2013486. Association for Computing Machinery, New York (2001)"},{"key":"32_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"421","DOI":"10.1007\/11604686_37","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"R.M. McConnell","year":"2005","unstructured":"McConnell, R.M., de Montgolfier, F.: Algebraic operations on PQ trees and modular decomposition trees. In: Kratsch, D. (ed.) WG 2005. LNCS, vol.\u00a03787, pp. 421\u2013432. Springer, Heidelberg (2005)"},{"key":"32_CR12","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1007\/s00453-003-1032-7","volume":"37","author":"R.M. McConnell","year":"2003","unstructured":"McConnell, R.M.: Linear-time recognition of circular-arc graphs. Algorithmica\u00a037, 93\u2013147 (2003)","journal-title":"Algorithmica"},{"key":"32_CR13","first-page":"866","volume-title":"SODA 2002","author":"R.M. McConnell","year":"2002","unstructured":"McConnell, R.M., Spinrad, J.P.: Construction of probe interval models. In: SODA 2002, pp. 866\u2013875. Association for Computing Machinery, New York (2002)"},{"key":"32_CR14","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1016\/S0166-218X(98)00077-8","volume":"88","author":"F.R. McMorris","year":"1998","unstructured":"McMorris, F.R., Wang, C., Zhang, P.: On probe interval graphs. Discrete Applied Mathematics\u00a088, 315\u2013324 (1998)","journal-title":"Discrete Applied Mathematics"},{"key":"32_CR15","doi-asserted-by":"publisher","first-page":"266","DOI":"10.1137\/0205021","volume":"5","author":"D. Rose","year":"1976","unstructured":"Rose, D., Tarjan, R.E., Lueker, G.S.: Algorithmic aspects of vertex elimination on graphs. SIAM J. Comput.\u00a05, 266\u2013283 (1976)","journal-title":"SIAM J. Comput."},{"key":"32_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"859","DOI":"10.1007\/978-3-540-30551-4_73","volume-title":"Algorithms and Computation","author":"R. Uehara","year":"2004","unstructured":"Uehara, R.: Canonical data structure for interval probe graphs. In: Fleischer, R., Trippen, G. (eds.) ISAAC 2004. LNCS, vol.\u00a03341, pp. 859\u2013870. Springer, Heidelberg (2004)"},{"key":"32_CR17","unstructured":"Zhang, P.: United states patent 5667970: Method of mapping DNA fragments (July 3, 2000)"}],"container-title":["Lecture Notes in Computer Science","Algorithms - ESA 2009"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-04128-0_32","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,9]],"date-time":"2019-03-09T14:38:22Z","timestamp":1552142302000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-04128-0_32"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642041273","9783642041280"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-04128-0_32","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}