{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T06:24:26Z","timestamp":1759991066909},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642114083"},{"type":"electronic","value":"9783642114090"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-11409-0_7","type":"book-chapter","created":{"date-parts":[[2009,12,3]],"date-time":"2009-12-03T08:12:27Z","timestamp":1259827947000},"page":"77-87","source":"Crossref","is-referenced-by-count":2,"title":["Fully Dynamic Representations of Interval Graphs"],"prefix":"10.1007","author":[{"given":"Christophe","family":"Crespelle","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"3","key":"7_CR1","doi-asserted-by":"crossref","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(3), 335\u2013379 (1976)","journal-title":"J. Comput. Syst. Sci."},{"key":"7_CR2","unstructured":"Crespelle, C.: Dynamic representations of interval graphs (manuscript) (2009), http:\/\/www-npa.lip6.fr\/~crespell\/publications\/DynInt_long.pdf"},{"key":"7_CR3","unstructured":"Crespelle, C., Paul, C.: Fully dynamic algorithm for recognition and modular decomposition of permutation graphs. Algorithmica, http:\/\/www.springerlink.com\/content\/u6x0054g3h348810\/ ; Ext. abs. in WG 2005"},{"issue":"12","key":"7_CR4","doi-asserted-by":"publisher","first-page":"1722","DOI":"10.1016\/j.dam.2006.03.005","volume":"154","author":"C. Crespelle","year":"2006","unstructured":"Crespelle, C., Paul, C.: Fully dynamic recognition algorithm and certificate for directed cographs. Discrete Applied Mathematics\u00a0154(12), 1722\u20131741 (2006); Ext. abs. in WG 2004","journal-title":"Discrete Applied Mathematics"},{"key":"7_CR5","doi-asserted-by":"crossref","first-page":"539","DOI":"10.4153\/CJM-1964-055-5","volume":"16","author":"P.C. Gilmore","year":"1964","unstructured":"Gilmore, P.C., Hoffman, A.J.: A characterization of comparability graphs and of interval graphs. Canad. J. Math.\u00a016, 539\u2013548 (1964)","journal-title":"Canad. J. Math."},{"issue":"1","key":"7_CR6","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1137\/S0097539700372216","volume":"31","author":"P. Hell","year":"2002","unstructured":"Hell, P., Shamir, R., Sharan, R.: A fully dynamic algorithm for recognizing and representing proper interval graphs. SIAM J. Comput.\u00a031(1), 289\u2013305 (2002)","journal-title":"SIAM J. Comput."},{"key":"7_CR7","doi-asserted-by":"crossref","unstructured":"Hsu, W.-L.: On-line recognition of interval graphs in O(m\u2009+\u2009nlog n) time. In: Combinatorics and Computer Science, pp. 27\u201338 (1996)","DOI":"10.1007\/3-540-61576-8_70"},{"key":"7_CR8","unstructured":"Ibarra, L.: Fully dynamic algorithms for chordal graphs. In: SODA, pp. 923\u2013924 (1999)"},{"key":"7_CR9","unstructured":"Ibarra, L.: A fully dynamic algorithm for recognizing interval graphs using the clique-separator graph. Tech. Report DCS-263-IR, Dept. of Computer Science, University of Victoria (2001)"},{"key":"7_CR10","series-title":"Lecture Notes in Computer Science","first-page":"143","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"N. Korte","year":"1995","unstructured":"Korte, N., M\u00f6hring, R.H.: Transitive orientation of graphs with side constraints. In: Nagl, M. (ed.) WG 1995. LNCS, vol.\u00a01017, pp. 143\u2013160. Springer, Heidelberg (1995)"},{"key":"7_CR11","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. Comput.\u00a018, 68\u201381 (1989)","journal-title":"SIAM J. Comput."},{"key":"7_CR12","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":"7_CR13","first-page":"257","volume":"19","author":"R.H. M\u00f6hring","year":"1984","unstructured":"M\u00f6hring, R.H., Radermacher, F.J.: Substitution decomposition for discrete structures and connections with combinatorial optimization. Annals of Discrete Mathematics\u00a019, 257\u2013356 (1984)","journal-title":"Annals of Discrete Mathematics"},{"issue":"1","key":"7_CR14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/58562.59300","volume":"36","author":"J.H. Muller","year":"1989","unstructured":"Muller, J.H., Spinrad, J.P.: Incremental modular decomposition algorithm. JACM\u00a036(1), 1\u201319 (1989)","journal-title":"JACM"},{"key":"7_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1007\/11917496_23","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"S.D. Nikolopoulos","year":"2006","unstructured":"Nikolopoulos, S.D., Palios, L., Papadopoulos, C.: A fully dynamic algorithm for the recognition of p 4-sparse graphs. In: Fomin, F.V. (ed.) WG 2006. LNCS, vol.\u00a04271, pp. 256\u2013268. Springer, Heidelberg (2006)"},{"key":"7_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"344","DOI":"10.1007\/978-3-540-70918-3_30","volume-title":"STACS 2007","author":"M. Tedder","year":"2007","unstructured":"Tedder, M., Corneil, D.G.: An optimal, edges-only fully dynamic algorithm for distance-hereditary graphs. In: Thomas, W., Weil, P. (eds.) STACS 2007. LNCS, vol.\u00a04393, pp. 344\u2013355. Springer, Heidelberg (2007)"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-11409-0_7.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,23]],"date-time":"2020-11-23T21:40:22Z","timestamp":1606167622000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-11409-0_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642114083","9783642114090"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-11409-0_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}