{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:47:53Z","timestamp":1725662873709},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540107040"},{"type":"electronic","value":"9783540386612"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1981]]},"DOI":"10.1007\/3-540-10704-5_15","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T17:14:31Z","timestamp":1330190071000},"page":"171-181","source":"Crossref","is-referenced-by-count":1,"title":["Algorithms for some intersection graphs"],"prefix":"10.1007","author":[{"given":"T.","family":"Kashiwabara","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,26]]},"reference":[{"key":"15_CR1","unstructured":"F. Harary, Graph theory, Addison-Wesley, Reading Massachusetts (1972)."},{"key":"15_CR2","doi-asserted-by":"crossref","first-page":"597","DOI":"10.1016\/0022-247X(70)90282-9","volume":"32","author":"D. J. Rose","year":"1970","unstructured":"D.J. Rose, Triangulated graphs and the elimination process, J. Math. Anal. Appl., 32, 597\u2013609 (1970).","journal-title":"J. Math. Anal. Appl."},{"issue":"9","key":"15_CR3","doi-asserted-by":"crossref","first-page":"675","DOI":"10.1109\/TCS.1979.1084695","volume":"CAS-26","author":"T. Ohtsuki","year":"1979","unstructured":"T. Ohtsuki, H. Mori, E.S. Kuh, T. Kashiwabara and T. Fujisawa, One-dimensional gate assignment and interval graphs, IEEE tran. on CAS Vol. CAS-26, No.9, 675\u2013684 (1979).","journal-title":"IEEE tran. on CAS"},{"key":"15_CR4","doi-asserted-by":"crossref","first-page":"8","DOI":"10.1016\/0095-8956(76)90022-8","volume":"21","author":"G. Ehrlich","year":"1976","unstructured":"G. Ehrlich, S. Even and R.E. Tarjan, Intersection graphs of curves in the plane, J. Combinatorial theory (B), 21, 8\u201320 (1976).","journal-title":"J. Combinatorial theory (B)"},{"key":"15_CR5","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1016\/B978-0-12-417750-5.50011-7","volume-title":"Queues, stacks and graphs, Theory of machines and computations","author":"S. Even","year":"1971","unstructured":"S. Even and A. Itai, Queues, stacks and graphs, Theory of machines and computations, Z. Kohavi and A. Paz, ed., Academic Press, New York, 71\u201386 (1971)."},{"key":"15_CR6","unstructured":"M.R. Garey and D.S. Johnson, Computers and intractability: A guide to the theory of NP-completeness, H. Freeman and Sons, San Francisco (1978)."},{"key":"15_CR7","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1002\/net.3230030305","volume":"3","author":"F. Gavril","year":"1973","unstructured":"F. Gavril, Algorithms for a maximum clique and a maximum independent set of a circle graph, Network, 3, 261\u2013273 (1973).","journal-title":"Network"},{"issue":"1","key":"15_CR8","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1137\/0209001","volume":"9","author":"A. Tucker","year":"1980","unstructured":"A. Tucker, An efficient test for circular-arc graphs, SIAM J. Comput., Vol.9, No.1, 1\u201324 (1980).","journal-title":"SIAM J. Comput."},{"key":"15_CR9","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1016\/0095-8956(74)90094-X","volume":"16","author":"F. Gavril","year":"1974","unstructured":"F. Gavril, The intersection graphs of subtrees in trees are exactly the chordal graphs, J. Combinatorial theory (B), 16, 47\u201356 (1974).","journal-title":"J. Combinatorial theory (B)"},{"issue":"2","key":"15_CR10","doi-asserted-by":"crossref","first-page":"266","DOI":"10.1137\/0205021","volume":"5","author":"D. J. Rose","year":"1976","unstructured":"D.J. Rose, R.E. Tarjan and G.S. Lueker, Algorithmic aspects of vertex elimination on graphs, SIAM J. Comput., Vol.5, No.2, 266\u2013283 (1976).","journal-title":"SIAM J. Comput."},{"key":"15_CR11","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1137\/0201013","volume":"1","author":"F. Gavril","year":"1972","unstructured":"F. Gavril, Algorithms for minimum coloring, maximum clique, minimum covering by cliques and maximum independent set of a chordal graph, SIAM J. Comput., 1, 180\u2013187 (1972).","journal-title":"SIAM J. Comput."},{"key":"15_CR12","unstructured":"T. Oyamada and T. Ohtsuki, Interval graphs and layout design of MOS arrays, IECE technical report CST75\u201383 (1975) (in Japanese)."},{"key":"15_CR13","unstructured":"T. Yoshida, An algorithm for obtaining a perfect order of an interval graph, monograph, Osaka University (1976) (in Japanese)."},{"key":"15_CR14","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. Computer and System Sciences, 13, 335\u2013379 (1976).","journal-title":"J. Computer and System Sciences"},{"key":"15_CR15","unstructured":"S. Fujishige, An efficient algorithm for solving the graph-realization problem by means of PQ-trees, Proceedings of 1979 ISCAS, IEEE catalog No. 79 CH 1421-7 CAS. 1012\u20131015 (1979)."},{"key":"15_CR16","unstructured":"S. Fujishige, An efficient algorithm for solving the graph-realization problem, IECE technical report CST78-136 (1979) (in Japanese)."},{"key":"15_CR17","unstructured":"A. Lempel, S. Even and I. Cederbaum, An algorithm for planarity testing of graphs, in \"Theory of graphs: international Symposium: Rome, July, 1966\" (P. Rosenstiehl, Ed.), 215\u2013232, Gordon and Breach, New York (1967)."},{"key":"15_CR18","volume-title":"PQ-tree algorithms, Ph.D. Dissertation, Department of Electrical Engineering and Computer Sciences","author":"K. S. Booth","year":"1975","unstructured":"K.S. Booth, PQ-tree algorithms, Ph.D. Dissertation, Department of Electrical Engineering and Computer Sciences, University of California Berkeley, California (1975)."},{"key":"15_CR19","unstructured":"T. Kashiwabara and T. Fujisawa, An NP-complete problem on interval graph, Proceedings of 1979 ISCAS, 82\u201383 (1979)."},{"key":"15_CR20","unstructured":"T. Kashiwabara, Y. Masaki and T. Fujisawa, Complexity of inter-valization of graphs, IECE technical report CST77-15 (1977) (in Japanese)."},{"key":"15_CR21","volume-title":"Efficient algorithms for chordal graphs and interval graphs, Ph.D. Dissertation, Program in Applied Mathematics and the Department of Electrical Engineering","author":"G. S. Lueker","year":"1975","unstructured":"G.S. Lueker, Efficient algorithms for chordal graphs and interval graphs, Ph.D. Dissertation, Program in Applied Mathematics and the Department of Electrical Engineering, Princeton University, Princeton N.J., (1975)."},{"key":"15_CR22","doi-asserted-by":"crossref","first-page":"45","DOI":"10.4064\/fm-51-1-45-64","volume":"51","author":"C. G. Lekkerkerker","year":"1962","unstructured":"C.G. Lekkerkerker and J. Ch. Boland, Representation of a finite graph by a set of intervals on the real line, Fundamenta Mathematicae, 51, 45\u201364 (1962).","journal-title":"Fundamenta Mathematicae"}],"container-title":["Lecture Notes in Computer Science","Graph Theory and Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-10704-5_15.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T20:38:47Z","timestamp":1619555927000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-10704-5_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1981]]},"ISBN":["9783540107040","9783540386612"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/3-540-10704-5_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1981]]}}}