{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T16:24:22Z","timestamp":1743092662184,"version":"3.40.3"},"publisher-location":"Cham","reference-count":20,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319905297"},{"type":"electronic","value":"9783319905303"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-319-90530-3_4","type":"book-chapter","created":{"date-parts":[[2018,4,24]],"date-time":"2018-04-24T07:23:53Z","timestamp":1524554633000},"page":"29-40","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Maintaining Chordal Graphs Dynamically: Improved Upper and Lower Bounds"],"prefix":"10.1007","author":[{"given":"Niranka","family":"Banerjee","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Venkatesh","family":"Raman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0636-9880","authenticated-orcid":false,"given":"Srinivasa Rao","family":"Satti","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,4,25]]},"reference":[{"key":"4_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1007\/11604686_39","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"A Berry","year":"2005","unstructured":"Berry, A., Sigayret, A., Spinrad, J.: Faster dynamic algorithms for chordal graphs, and an application to phylogeny. In: Kratsch, D. (ed.) WG 2005. LNCS, vol. 3787, pp. 445\u2013455. Springer, Heidelberg (2005). https:\/\/doi.org\/10.1007\/11604686_39"},{"issue":"3","key":"4_CR2","doi-asserted-by":"publisher","first-page":"437","DOI":"10.1137\/S0895480193253415","volume":"11","author":"A Brandst\u00e4dt","year":"1998","unstructured":"Brandst\u00e4dt, A., Dragan, F.F., Chepoi, V., Voloshin, V.I.: Dually chordal graphs. SIAM J. Discrete Math. 11(3), 437\u2013455 (1998)","journal-title":"SIAM J. Discrete Math."},{"issue":"3","key":"4_CR3","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/0012-365X(74)90002-8","volume":"9","author":"P Buneman","year":"1974","unstructured":"Buneman, P.: A characterisation of rigid circuit graphs. Discrete Math. 9(3), 205\u2013212 (1974)","journal-title":"Discrete Math."},{"unstructured":"Deshpande, A., Garofalakis, M.N., Jordan, M.I.: Efficient stepwise selection in decomposable models. In: UAI 2001: Proceedings of the 17th Conference in Uncertainty in Artificial Intelligence, University of Washington, Seattle, Washington, USA, 2\u20135 Aug 2001, pp. 128\u2013135 (2001)","key":"4_CR4"},{"key":"4_CR5","series-title":"Graduate Texts in Mathematics","volume-title":"Graph Theory","author":"R Diestel","year":"2012","unstructured":"Diestel, R.: Graph Theory. GTM, vol. 173, 4th edn. Springer, Heidelberg (2012)","edition":"4"},{"doi-asserted-by":"crossref","unstructured":"Dietz, P.F., Sleator, D.D.: Two algorithms for maintaining order in a list. In: Proceedings of the 19th Annual ACM Symposium on Theory of Computing 1987, New York, NY, USA, pp. 365\u2013372 (1987)","key":"4_CR6","DOI":"10.1145\/28395.28434"},{"issue":"3","key":"4_CR7","doi-asserted-by":"publisher","first-page":"514","DOI":"10.1145\/2402.322390","volume":"30","author":"R Fagin","year":"1983","unstructured":"Fagin, R.: Degrees of acyclicity for hypergraphs and relational database schemes. J. ACM 30(3), 514\u2013550 (1983)","journal-title":"J. ACM"},{"issue":"2","key":"4_CR8","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1137\/0201013","volume":"1","author":"F Gavril","year":"1972","unstructured":"Gavril, F.: Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph. SIAM J. Comput. 1(2), 180\u2013187 (1972)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"4_CR9","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. Comput. 31(1), 289\u2013305 (2001)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"4_CR10","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1007\/PL00009228","volume":"22","author":"MR Henzinger","year":"1998","unstructured":"Henzinger, M.R., Fredman, M.L.: Lower bounds for fully dynamic connectivity problems in graphs. Algorithmica 22(3), 351\u2013362 (1998)","journal-title":"Algorithmica"},{"issue":"3","key":"4_CR11","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1002\/jgt.3190050314","volume":"5","author":"E Howorka","year":"1981","unstructured":"Howorka, E.: A characterization of ptolemaic graphs. J. Graph Theory 5(3), 323\u2013331 (1981)","journal-title":"J. Graph Theory"},{"issue":"4","key":"4_CR12","doi-asserted-by":"publisher","first-page":"40: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 Trans. Algorithms 4(4), 40:1\u201340:20 (2008)","journal-title":"ACM Trans. Algorithms"},{"key":"4_CR13","doi-asserted-by":"publisher","first-page":"82","DOI":"10.1016\/j.tcs.2012.05.002","volume":"445","author":"M Mezzini","year":"2012","unstructured":"Mezzini, M.: Fully dynamic algorithm for chordal graphs with O(1) query-time and O(n$${}^{2})$$ update-time. Theor. Comput. Sci. 445, 82\u201392 (2012)","journal-title":"Theor. Comput. Sci."},{"issue":"7\u20139","key":"4_CR14","doi-asserted-by":"publisher","first-page":"958","DOI":"10.1016\/j.tcs.2009.10.004","volume":"411","author":"M Mezzini","year":"2010","unstructured":"Mezzini, M., Moscarini, M.: Simple algorithms for minimal triangulation of a graph and backward selection of a decomposable markov network. Theor. Comput. Sci. 411(7\u20139), 958\u2013966 (2010)","journal-title":"Theor. Comput. Sci."},{"key":"4_CR15","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1016\/j.endm.2008.06.050","volume":"31","author":"J Nesetril","year":"2008","unstructured":"Nesetril, J.: Structural properties of sparse graphs. Electron. Notes Discrete Math. 31, 247\u2013251 (2008)","journal-title":"Electron. Notes Discrete Math."},{"issue":"4","key":"4_CR16","doi-asserted-by":"publisher","first-page":"932","DOI":"10.1137\/S0097539705447256","volume":"35","author":"M Patrascu","year":"2006","unstructured":"Patrascu, M., Demaine, E.D.: Logarithmic lower bounds in the cell-probe model. SIAM J. Comput. 35(4), 932\u2013963 (2006)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"4_CR17","doi-asserted-by":"publisher","first-page":"266","DOI":"10.1137\/0205021","volume":"5","author":"DJ Rose","year":"1976","unstructured":"Rose, D.J., Tarjan, R.E., Lueker, G.S.: Algorithmic aspects of vertex elimination on graphs. SIAM J. Comput. 5(2), 266\u2013283 (1976)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"4_CR18","doi-asserted-by":"publisher","first-page":"566","DOI":"10.1137\/0213035","volume":"13","author":"RE 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. Comput. 13(3), 566\u2013579 (1984)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"4_CR19","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1002\/jgt.3190020311","volume":"2","author":"JR Walter","year":"1978","unstructured":"Walter, J.R.: Representations of chordal graphs as subtrees of a tree. J. Graph Theory 2(3), 265\u2013267 (1978)","journal-title":"J. Graph Theory"},{"issue":"3","key":"4_CR20","doi-asserted-by":"publisher","first-page":"615","DOI":"10.1145\/322261.322274","volume":"28","author":"AC-C Yao","year":"1981","unstructured":"Yao, A.C.-C.: Should tables be sorted? J. ACM 28(3), 615\u2013628 (1981)","journal-title":"J. ACM"}],"container-title":["Lecture Notes in Computer Science","Computer Science \u2013 Theory and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-90530-3_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,12]],"date-time":"2024-03-12T11:29:20Z","timestamp":1710242960000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-90530-3_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319905297","9783319905303"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-90530-3_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"value":"25 April 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CSR","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Computer Science Symposium in Russia","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Moscow","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Russia","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2018","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"6 June 2018","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"10 June 2018","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"csr2018","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/logic.pdmi.ras.ru\/csr2018\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}