{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T06:40:34Z","timestamp":1759992034508},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642002014"},{"type":"electronic","value":"9783642002021"}],"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-00202-1_17","type":"book-chapter","created":{"date-parts":[[2009,2,10]],"date-time":"2009-02-10T07:34:01Z","timestamp":1234251241000},"page":"190-201","source":"Crossref","is-referenced-by-count":5,"title":["A Fully Dynamic Graph Algorithm for Recognizing Proper Interval Graphs"],"prefix":"10.1007","author":[{"given":"Louis","family":"Ibarra","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"17_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-1-4613-8369-7_1","volume-title":"Graph Theory and Sparse Matrix Computation","author":"J.R.S. Blair","year":"1993","unstructured":"Blair, J.R.S., Peyton, B.: An introduction to chordal graphs and clique trees. In: Graph Theory and Sparse Matrix Computation, vol.\u00a056, pp. 1\u201329. Springer-Verlag, New York (1993)"},{"key":"17_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. Computer and System Sciences\u00a013, 335\u2013379 (1976)","journal-title":"J. Computer and System Sciences"},{"key":"17_CR3","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, 2nd edn. MIT Press and McGraw-Hill Book Co., Cambridge (2001)","edition":"2"},{"key":"17_CR4","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/0020-0190(95)00046-F","volume":"55","author":"D.G. Corneil","year":"1995","unstructured":"Corneil, D.G., Kim, H., Nataranjan, S., Olariu, S., Sprague, A.P.: Simple linear time recognition of unit interval graphs. Information Processing Letters\u00a055, 99\u2013104 (1995)","journal-title":"Information Processing Letters"},{"key":"17_CR5","unstructured":"Corneil, D.G., Olariu, S., Stewart, L.: The ultimate interval graph recognition algorithm? In: Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 175\u2013180 (1998)"},{"issue":"2","key":"17_CR6","doi-asserted-by":"publisher","first-page":"390","DOI":"10.1137\/S0097539792269095","volume":"25","author":"X. Deng","year":"1996","unstructured":"Deng, X., Hell, P., Huang, J.: Linear-time representation algorithms for proper circular-arc graphs and proper interval graphs. SIAM J. Computing\u00a025(2), 390\u2013403 (1996)","journal-title":"SIAM J. Computing"},{"key":"17_CR7","volume-title":"Algorithms and Theory of Computation Handbook","author":"D. Eppstein","year":"1998","unstructured":"Eppstein, D., Galil, Z., Italiano, G.F.: Dynamic graph algorithms. In: Atallah, M.J. (ed.) Algorithms and Theory of Computation Handbook, ch.\u00a08. CRC Press, Boca Raton (1998)"},{"key":"17_CR8","volume-title":"Handbook of Discrete and Combinatorial Mathematics","author":"J. Feigenbaum","year":"1999","unstructured":"Feigenbaum, J., Kannan, S.: Dynamic graph algorithms. In: Rosen (ed.) Handbook of Discrete and Combinatorial Mathematics, ch.\u00a017. CRC Press, Boca Raton (1999)"},{"key":"17_CR9","volume-title":"Annals of Discrete Mathematics","author":"M.C. Golumbic","year":"2004","unstructured":"Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. In: Annals of Discrete Mathematics, vol.\u00a057. Elsevier B.V., Amsterdam (2004)"},{"key":"17_CR10","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1137\/S0097539700372216","volume":"31","author":"P. Hell","year":"2001","unstructured":"Hell, P., Shamir, R., Sharan, R.: A fully dynamic algorithm for recognizing and representing proper interval graphs. SIAM J. Computing\u00a031, 289\u2013305 (2001)","journal-title":"SIAM J. Computing"},{"key":"17_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1007\/3-540-61576-8_70","volume-title":"Combinatorics and Computer Science","author":"W.L. Hsu","year":"1996","unstructured":"Hsu, W.L.: On-line recognition of interval graphs. In: Deza, M., Manoussakis, I., Euler, R. (eds.) CCS 1995. LNCS, vol.\u00a01120, pp. 27\u201338. Springer, Heidelberg (1996)"},{"issue":"3","key":"17_CR12","doi-asserted-by":"publisher","first-page":"1004","DOI":"10.1137\/S0097539792224814","volume":"28","author":"W.L. Hsu","year":"1999","unstructured":"Hsu, W.L., Ma, T.H.: Fast and simple algorithms for recognizing chordal comparability graphs and interval graphs. SIAM J. Computing\u00a028(3), 1004\u20131020 (1999)","journal-title":"SIAM J. Computing"},{"key":"17_CR13","unstructured":"Ibarra, L.: The clique-separator graph for chordal graphs (submitted, 2006), http:\/\/facweb.cs.depaul.edu\/ibarra\/research.htm"},{"key":"17_CR14","unstructured":"Ibarra, L.: A fully dynamic graph algorithm for recognizing interval graphs (submitted, 2007), http:\/\/facweb.cs.depaul.edu\/ibarra\/research.htm"},{"issue":"4","key":"17_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1383369.1383371","volume":"4","author":"L. Ibarra","year":"2008","unstructured":"Ibarra, L.: Fully dynamic algorithms for chordal graphs and split graphs. ACM Transactions on Algorithms\u00a04(4), 1\u201320 (2008), http:\/\/facweb.cs.depaul.edu\/ibarra\/research.htm","journal-title":"ACM Transactions on Algorithms"},{"key":"17_CR16","doi-asserted-by":"crossref","unstructured":"Ibarra, L.: A simple algorithm to find Hamiltonian cycles in proper interval graphs (submitted, 2008), http:\/\/facweb.cs.depaul.edu\/ibarra\/research.htm","DOI":"10.1016\/j.ipl.2009.07.010"},{"key":"17_CR17","doi-asserted-by":"crossref","unstructured":"Ibarra, L.: A simple fully dynamic graph algorithm for recognizing proper interval graphs (submitted, 2008), http:\/\/facweb.cs.depaul.edu\/ibarra\/research.htm","DOI":"10.1007\/978-3-642-00202-1_17"},{"key":"17_CR18","doi-asserted-by":"publisher","first-page":"434","DOI":"10.1016\/0196-6774(85)90012-4","volume":"6","author":"D.S. Johnson","year":"1985","unstructured":"Johnson, D.S.: The NP-completeness column: an ongoing guide. J. Algorithms\u00a06, 434\u2013451 (1985)","journal-title":"J. Algorithms"},{"issue":"1","key":"17_CR19","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1137\/0218005","volume":"18","author":"N. Korte","year":"1989","unstructured":"Korte, N., M\u00f6hring, R.H.: An incremental linear-time algorithm for recognizing interval graphs. SIAM J. Computing\u00a018(1), 68\u201381 (1989)","journal-title":"SIAM J. Computing"},{"key":"17_CR20","doi-asserted-by":"crossref","unstructured":"McKee, T.A., McMorris, F.R.: Topics in Intersection Graph Theory, Philadelphia. Society for Industrial and Applied Mathematics (1999) (Monograph)","DOI":"10.1137\/1.9780898719802"},{"issue":"2","key":"17_CR21","doi-asserted-by":"publisher","first-page":"266","DOI":"10.1137\/0205021","volume":"5","author":"D.J. Rose","year":"1976","unstructured":"Rose, D.J., Tarjan, R.E., Lueker, G.S.: Algorithmic aspects of vertex elimination on graphs. SIAM J. Computing\u00a05(2), 266\u2013283 (1976)","journal-title":"SIAM J. Computing"},{"issue":"3","key":"17_CR22","doi-asserted-by":"publisher","first-page":"566","DOI":"10.1137\/0213035","volume":"13","author":"R.E. Tarjan","year":"1984","unstructured":"Tarjan, R.E., Yannakakis, M.: Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs. SIAM J. Computing\u00a013(3), 566\u2013579 (1984)","journal-title":"SIAM J. Computing"}],"container-title":["Lecture Notes in Computer Science","WALCOM: Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-00202-1_17","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,17]],"date-time":"2019-05-17T23:07:38Z","timestamp":1558134458000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-00202-1_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642002014","9783642002021"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-00202-1_17","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}