{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:12:49Z","timestamp":1725664369708},"publisher-location":"Berlin, Heidelberg","reference-count":10,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540615767"},{"type":"electronic","value":"9783540706274"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1996]]},"DOI":"10.1007\/3-540-61576-8_70","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T16:57:57Z","timestamp":1330275477000},"page":"27-38","source":"Crossref","is-referenced-by-count":6,"title":["On-line recognition of interval graphs in O(m+nlog n) time"],"prefix":"10.1007","author":[{"given":"Wen-Lian","family":"Hsu","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,2]]},"reference":[{"key":"4_CR1","doi-asserted-by":"crossref","unstructured":"K. S. Booth and G. S. Lueker, Linear algorithms to recognize interval graphs and test for the consecutive ones property, Proc. 7th ACM Symp. Theory of Computing, (1975), 255\u2013265.","DOI":"10.1145\/800116.803776"},{"key":"4_CR2","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1016\/S0022-0000(76)80045-1","volume":"13","author":"K. S. Booth","year":"1976","unstructured":"K. S. Booth and G. S. Lueker, Testing for the consecutive ones property, interval graphs and graph planarity using PQ-tree algorithms, J. Comput. Syst. Sci. 13, (1976), 335\u2013379.","journal-title":"J. Comput. Syst. Sci."},{"key":"4_CR3","doi-asserted-by":"crossref","first-page":"835","DOI":"10.2140\/pjm.1965.15.835","volume":"15","author":"D. R. Fulkerson","year":"1965","unstructured":"D. R. Fulkerson and O. A. Gross, Incidence Matrices and Interval Graphs, Pacific J. Math. 15, (1965), 835\u2013855.","journal-title":"Pacific J. Math."},{"key":"4_CR4","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_CR5","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1137\/S0097539793260726","volume":"24","author":"W. L. Hsu","year":"1995","unstructured":"W. L. Hsu, O(mn) Recognition and Isomorphism Algorithms for Circular-Arc Graphs, SIAM J. Comput. 24, (1995), 411\u2013439.","journal-title":"SIAM J. Comput."},{"key":"4_CR6","doi-asserted-by":"crossref","first-page":"52","DOI":"10.1007\/3-540-54945-5_49","volume":"557","author":"W. L. Hsu","year":"1991","unstructured":"W. L. Hsu and C. H. Ma, Fast and Simple Algorithms for Recognizing Chordal Comparability Graphs and Interval Graphs, Lecture Notes in Computer Science 557, 52\u201360, (1991), to appear in SIAM J. Comput.","journal-title":"Lecture Notes in Computer Science"},{"key":"4_CR7","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1007\/3-540-56402-0_31","volume":"657","author":"W. L. Hsu","year":"1992","unstructured":"W. L. Hsu, A simple test for interval graphs, Lecture Notes in Computer Science 657, (1992), 11\u201316.","journal-title":"Lecture Notes in Computer Science"},{"key":"4_CR8","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1137\/0218005","volume":"18","author":"N. Korte","year":"1989","unstructured":"N. Korte and R. H. M\u00f6hring, An incremental linear time algorithm for recognizing interval graphs, SIAM J. Comput. 18, (1989), 68\u201381.","journal-title":"SIAM J. Comput."},{"key":"4_CR9","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1145\/322123.322125","volume":"26","author":"G. S. Lueker","year":"1979","unstructured":"G. S. Lueker and K. S. Booth, Interval graph isomorphism, JACM 26, (1979), 195.","journal-title":"JACM"},{"key":"4_CR10","doi-asserted-by":"crossref","first-page":"658","DOI":"10.1137\/0214048","volume":"14","author":"J. Spinrad","year":"1985","unstructured":"J. Spinrad, On Comparability and Permutation Graphs, SIAM J. Comput. 14 (1985), 658\u2013670.","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Combinatorics and Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-61576-8_70.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T21:34:32Z","timestamp":1619559272000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-61576-8_70"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540615767","9783540706274"],"references-count":10,"URL":"https:\/\/doi.org\/10.1007\/3-540-61576-8_70","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1996]]}}}