{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T06:13:05Z","timestamp":1759990385003},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540709176"},{"type":"electronic","value":"9783540709183"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-70918-3_30","type":"book-chapter","created":{"date-parts":[[2007,5,23]],"date-time":"2007-05-23T23:41:23Z","timestamp":1179963683000},"page":"344-355","source":"Crossref","is-referenced-by-count":2,"title":["An Optimal, Edges-Only Fully Dynamic Algorithm for Distance-Hereditary Graphs"],"prefix":"10.1007","author":[{"given":"Marc","family":"Tedder","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Derek","family":"Corneil","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"30_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1007\/978-3-540-30559-0_8","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"C. Crespelle","year":"2004","unstructured":"Crespelle, C., Paul, C.: Fully dynamic algorithm and certificate for directed cographs. In: Hromkovi\u010d, J., Nagl, M., Westfechtel, B. (eds.) WG 2004. LNCS, vol.\u00a03353, pp. 93\u2013104. Springer, Heidelberg (2004)"},{"key":"30_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1007\/11604686_4","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"C. Crespelle","year":"2005","unstructured":"Crespelle, C., Paul, C.: Fully dynamic algorithm for modular decomposition and recognition of permutation graphs. In: Kratsch, D. (ed.) WG 2005. LNCS, vol.\u00a03787, pp. 38\u201348. Springer, Heidelberg (2005)"},{"key":"30_CR3","doi-asserted-by":"publisher","first-page":"926","DOI":"10.1137\/0214065","volume":"14","author":"D. Corneil","year":"1985","unstructured":"Corneil, D., Perl, Y., Stewart, L.: A linear recognition algorithm for cographs. Siam J. Comput.\u00a014, 926\u2013934 (1985)","journal-title":"Siam J. Comput."},{"key":"30_CR4","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. Comput.\u00a025, 390\u2013403 (1996)","journal-title":"SIAM J. Comput."},{"key":"30_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","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 O(m\u2009+\u2009nlog\n                  n) time. In: Deza, M., Manoussakis, I., Euler, R. (eds.) CCS 1995. LNCS, vol.\u00a01120, pp. 27\u201338. Springer, Heidelberg (1996)"},{"key":"30_CR6","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.\u00a031, 289\u2013305 (2001)","journal-title":"SIAM J. Comput."},{"key":"30_CR7","unstructured":"Ibarra, L.: A fully dynamic algorithm for recognizing interval graphs using the clique-separator graph. Technical report, University of Victoria (2001)"},{"key":"30_CR8","first-page":"923","volume-title":"SODA \u201999: Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms","author":"L. Ibarra","year":"1999","unstructured":"Ibarra, L.: Fully dynamic algorithms for chordal graphs. In: SODA \u201999: Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, pp. 923\u2013924. SIAM, Philadelphia (1999)"},{"key":"30_CR9","doi-asserted-by":"publisher","first-page":"381","DOI":"10.1137\/0221027","volume":"21","author":"B. Jamison","year":"1992","unstructured":"Jamison, B., Olariu, S.: Recognizing P\n                  4-sparse graphs in linear time. Siam J. Comput\u00a021, 381\u2013406 (1992)","journal-title":"Siam J. Comput"},{"key":"30_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","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\n                  4-sparse graphs. In: Fomin, F.V. (ed.) WG 2006. LNCS, vol.\u00a04271, Springer, Heidelberg (2006)"},{"key":"30_CR11","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1016\/S0166-218X(03)00448-7","volume":"136","author":"R. Shamir","year":"2004","unstructured":"Shamir, R., Sharan, R.: A fully dynamic algorithm for modular decomposition and recognition of cographs. Discrete Applied Mathematics\u00a0136, 329\u2013340 (2004)","journal-title":"Discrete Applied Mathematics"},{"key":"30_CR12","volume-title":"Introduction to Graph Theory","author":"D.B. West","year":"2001","unstructured":"West, D.B.: Introduction to Graph Theory, 2nd edn. Prentice Hall, Upper Saddle River (2001)","edition":"2"},{"key":"30_CR13","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898719796","volume-title":"Graph classes: a survey","author":"A. Brandstadt","year":"1999","unstructured":"Brandstadt, A., Le, V.B., Spinrad, J.P.: Graph classes: a survey. SIAM, Philadelphia (1999)"},{"key":"30_CR14","first-page":"26","volume-title":"SODA \u201997: Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms","author":"E. Dahlhaus","year":"1997","unstructured":"Dahlhaus, E., Gustedt, J., McConnell, R.M.: Efficient and practical modular decomposition. In: SODA \u201997: Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, pp. 26\u201335. SIAM, Philadelphia (1997)"},{"key":"30_CR15","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1016\/0095-8956(86)90043-2","volume":"41","author":"H. Bandelt","year":"1986","unstructured":"Bandelt, H., Mulder, H.: Distance-hereditary graphs. J. Comb. Theory Ser. B\u00a041, 182\u2013208 (1986)","journal-title":"J. Comb. Theory Ser. B"},{"key":"30_CR16","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/0166-218X(90)90131-U","volume":"27","author":"P.L. Hammer","year":"1990","unstructured":"Hammer, P.L., Maffray, F.: Completely separable graphs. Discrete Appl. Math.\u00a027, 85\u201399 (1990)","journal-title":"Discrete Appl. Math."},{"key":"30_CR17","doi-asserted-by":"publisher","first-page":"521","DOI":"10.1137\/0217032","volume":"17","author":"A. D\u2019Atri","year":"1988","unstructured":"D\u2019Atri, A., Moscarini, M.: Distance-hereditary graphs, steiner trees, and connected domination. SIAM J. Comput.\u00a017, 521\u2013538 (1988)","journal-title":"SIAM J. Comput."},{"key":"30_CR18","unstructured":"Tedder, M.: An optimal algorithm recognizing distance-hereditary graphs under a sequence of edge deletions. Master\u2019s thesis, University of Toronto (2006)"},{"key":"30_CR19","unstructured":"Tedder, M.: An optimal, edges-only fully-dynamic algorithm recognizing distance-hereditary graphs. In preparation (2006)"}],"container-title":["Lecture Notes in Computer Science","STACS 2007"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-70918-3_30.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,19]],"date-time":"2020-11-19T05:11:51Z","timestamp":1605762711000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-70918-3_30"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540709176","9783540709183"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-70918-3_30","relation":{},"subject":[]}}