{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T06:37:54Z","timestamp":1759991874518},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2009,1,15]],"date-time":"2009-01-15T00:00:00Z","timestamp":1231977600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2010,10]]},"DOI":"10.1007\/s00453-008-9273-0","type":"journal-article","created":{"date-parts":[[2009,1,14]],"date-time":"2009-01-14T19:06:12Z","timestamp":1231959972000},"page":"405-432","source":"Crossref","is-referenced-by-count":14,"title":["Fully Dynamic Algorithm for Recognition and Modular Decomposition of Permutation Graphs"],"prefix":"10.1007","volume":"58","author":[{"given":"Christophe","family":"Crespelle","sequence":"first","affiliation":[]},{"given":"Christophe","family":"Paul","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2009,1,15]]},"reference":[{"key":"9273_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"779","DOI":"10.1007\/11561071_69","volume-title":"13th European Symposium on Algorithm (ESA\u201905)","author":"A. Bergeron","year":"2005","unstructured":"Bergeron, A., Chauve, C., de Montgolfier, F., Raffinot, M.: Computing common intervals of K permutations, with applications to modular decomposition of graphs. In: 13th European Symposium on Algorithm (ESA\u201905). Lecture Notes in Computer Science, vol. 3669, pp. 779\u2013790. Springer, New York (2005)"},{"key":"9273_CR2","series-title":"SIAM Monographs on Discrete Mathematics and Applications","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898719796","volume-title":"Graph Classes: A Survey","author":"A. Brandst\u00e4dt","year":"1999","unstructured":"Brandst\u00e4dt, A., Le, V.B., Spinrad, J.P.: Graph Classes: A Survey. SIAM Monographs on Discrete Mathematics and Applications. Society for Industrial and Applied Mathematics, Philadelphia (1999)"},{"key":"9273_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1007\/11602613_16","volume-title":"16th International Symposium on Algorithms and Computation (ISAAC\u201905)","author":"B.M. Bui-Xuan","year":"2005","unstructured":"Bui-Xuan, B.M., Habib, M., Paul, C.: Revisiting uno and yagiura\u2019s algorithm. In: 16th International Symposium on Algorithms and Computation (ISAAC\u201905). Lecture Notes in Computer Science, vol. 3827, pp. 146\u2013155. Springer, New York (2005)"},{"issue":"4","key":"9273_CR4","doi-asserted-by":"crossref","first-page":"926","DOI":"10.1137\/0214065","volume":"14","author":"D.G. Corneil","year":"1985","unstructured":"Corneil, D.G., Perl, Y., Stewart, L.K.: A linear time recognition algorithm for cographs. SIAM J. Comput. 14(4), 926\u2013934 (1985)","journal-title":"SIAM J. Comput."},{"key":"9273_CR5","series-title":"Lecture Notes in Computer Science","volume-title":"31th International Workshop on Graph Theoretical Concepts in Computer Science (WG\u201905)","author":"C. Crespelle","year":"2005","unstructured":"Crespelle, C., Paul, C.: Fully dynamic algorithm for recognition and modular decomposition of permutation graphs. In: 31th International Workshop on Graph Theoretical Concepts in Computer Science (WG\u201905). Lecture Notes in Computer Science, vol. 3787. Springer, New York (2005)"},{"issue":"12","key":"9273_CR6","doi-asserted-by":"crossref","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 Appl. Math. 154(12), 1722\u20131741 (2006)","journal-title":"Discrete Appl. Math."},{"key":"9273_CR7","unstructured":"de Montgolfier, F.: D\u00e9composition modulaire des graphes\u2014Th\u00e9orie, extensions et algorithmes. Ph.D. thesis, Universit\u00e9 de Montpellier 2, France (2003)"},{"issue":"5","key":"9273_CR8","doi-asserted-by":"crossref","first-page":"956","DOI":"10.1137\/S0097539794280736","volume":"25","author":"G. Battista Di","year":"1996","unstructured":"Di Battista, G., Tamassia, R.: On-line planarity testing. SIAM J. Comput. 25(5), 956\u2013997 (1996)","journal-title":"SIAM J. Comput."},{"key":"9273_CR9","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1006\/jagm.1994.1013","volume":"16","author":"A. Ehrenfeucht","year":"1994","unstructured":"Ehrenfeucht, A., Gabow, H.N., McConnell, R.M., Sullivan, S.J.: An O(n 2) divide-and-conquer algorithm for the prime tree decomposition of two-structures and modular decomposition of graphs. J.\u00a0Algorithms 16, 283\u2013294 (1994)","journal-title":"J.\u00a0Algorithms"},{"issue":"1","key":"9273_CR10","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1137\/S0097539794269072","volume":"28","author":"D. Eppstein","year":"1998","unstructured":"Eppstein, D., Galil, Z., Italiano, G.F., Spencer, T.H.: Separator-based sparsification II: Edge and vertex connectivity. SIAM J. Comput. 28(1), 341\u2013381 (1998)","journal-title":"SIAM J. Comput."},{"key":"9273_CR11","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1007\/BF02020961","volume":"18","author":"T. Gallai","year":"1967","unstructured":"Gallai, T.: Transitiv orientierbare graphen. Acta Math. Acad. Sci. Hung. 18, 25\u201366 (1967)","journal-title":"Acta Math. Acad. Sci. Hung."},{"key":"9273_CR12","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"M.C. Golumbic","year":"1980","unstructured":"Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Academic, New York (1980)"},{"issue":"1","key":"9273_CR13","doi-asserted-by":"crossref","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."},{"key":"9273_CR14","unstructured":"Ibarra, L.: Fully dynamic algorithms for chordal graphs. In: 10th ACM-SIAM Annual Symposium on Discrete Algorithm (SODA\u201999), pp. 923\u2013924 (1999)"},{"key":"9273_CR15","unstructured":"McConnell, R.M., Spinrad, J.: Linear-time transitive orientation. In: 8th ACM-SIAM Annual Symposium on Discrete Algorithm (SODA\u201997), pp. 19\u201325 (1997)"},{"issue":"1\u20133","key":"9273_CR16","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/S0012-365X(98)00319-7","volume":"201","author":"R.M. McConnell","year":"1999","unstructured":"McConnell, R.M., Spinrad, J.: Modular decomposition and transitive orientation. Discrete Math. 201(1\u20133), 189\u2013241 (1999)","journal-title":"Discrete Math."},{"key":"9273_CR17","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1007\/BF02022041","volume":"4","author":"R.H. M\u00f6hring","year":"1985","unstructured":"M\u00f6hring, R.H.: Algorithmic aspect of the substitution decomposition in optimization over relations, set systems and boolean functions. Ann. Oper. Res. 4, 195\u2013225 (1985)","journal-title":"Ann. Oper. Res."},{"key":"9273_CR18","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. Ann. Discrete Math. 19, 257\u2013356 (1984)","journal-title":"Ann. Discrete Math."},{"issue":"1","key":"9273_CR19","doi-asserted-by":"crossref","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. J. Assoc. Comput. Mach. 36(1), 1\u201319 (1989)","journal-title":"J. Assoc. Comput. Mach."},{"key":"9273_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"256","DOI":"10.1007\/11917496_23","volume-title":"32nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG\u201906)","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: 32nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG\u201906). Lecture Notes in Computer Science, vol. 4271, pp. 256\u2013268. Springer, New York (2006)"},{"issue":"2\u20133","key":"9273_CR21","doi-asserted-by":"crossref","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 Appl. Math. 136(2\u20133), 329\u2013340 (2004)","journal-title":"Discrete Appl. Math."},{"key":"9273_CR22","series-title":"Fields Institute Monographs","doi-asserted-by":"crossref","DOI":"10.1090\/fim\/019","volume-title":"Efficient Graph Representations","author":"J. Spinrad","year":"2003","unstructured":"Spinrad, J.: Efficient Graph Representations. Fields Institute Monographs, vol. 19. American Mathematical Society, Providence (2003)"},{"issue":"2","key":"9273_CR23","doi-asserted-by":"crossref","first-page":"290","DOI":"10.1007\/s004539910014","volume":"26","author":"T. Uno","year":"2000","unstructured":"Uno, T., Yagiura, M.: Fast algorithms to enumerate all common intervals of two permutations. Algorithmica 26(2), 290\u2013309 (2000)","journal-title":"Algorithmica"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-008-9273-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-008-9273-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-008-9273-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T13:45:03Z","timestamp":1559137503000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-008-9273-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,1,15]]},"references-count":23,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2010,10]]}},"alternative-id":["9273"],"URL":"https:\/\/doi.org\/10.1007\/s00453-008-9273-0","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,1,15]]}}}