{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T05:58:33Z","timestamp":1725861513913},"publisher-location":"Cham","reference-count":27,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319426334"},{"type":"electronic","value":"9783319426341"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"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":[[2016]]},"DOI":"10.1007\/978-3-319-42634-1_5","type":"book-chapter","created":{"date-parts":[[2016,7,19]],"date-time":"2016-07-19T11:50:21Z","timestamp":1468929021000},"page":"55-66","source":"Crossref","is-referenced-by-count":0,"title":["Polynomial-Time Algorithm for Isomorphism of Graphs with Clique-Width at Most Three"],"prefix":"10.1007","author":[{"given":"Bireswar","family":"Das","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Murali Krishna","family":"Enduri","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"I. Vinod","family":"Reddy","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,7,20]]},"reference":[{"key":"5_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"34","DOI":"10.1007\/3-540-10854-8_4","volume-title":"Fundamentals of Computation Theory","author":"L Babai","year":"1981","unstructured":"Babai, L.: Moderately exponential bound for graph isomorphism. In: G\u00e9cseg, F. (ed.) Fundamentals of Computation Theory. LNCS, vol. 117, pp. 34\u201350. Springer, Heidelberg (1981)"},{"key":"5_CR2","unstructured":"Babai, L.: Graph isomorphism in quasipolynomial time (2015). arXiv preprint arXiv:1512.03547"},{"issue":"4","key":"5_CR3","doi-asserted-by":"crossref","first-page":"631","DOI":"10.1016\/0196-6774(90)90013-5","volume":"11","author":"HL Bodlaender","year":"1990","unstructured":"Bodlaender, H.L.: Polynomial algorithms for graph isomorphism and chromatic index on partial $$k$$ -trees. J. Algorithms 11(4), 631\u2013643 (1990)","journal-title":"J. Algorithms"},{"key":"5_CR4","unstructured":"Bonamy, M.: A small report on graph and tree isomorphism (2010). http:\/\/bit.ly\/1ySeNBn"},{"issue":"2","key":"5_CR5","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1016\/0020-0190(87)90232-8","volume":"25","author":"RB Boppana","year":"1987","unstructured":"Boppana, R.B., Hastad, J., Zachos, S.: Does co-NP have short interactive proofs? Inf. Process. Lett. 25(2), 127\u2013132 (1987)","journal-title":"Inf. Process. Lett."},{"issue":"6","key":"5_CR6","doi-asserted-by":"crossref","first-page":"834","DOI":"10.1016\/j.dam.2011.03.020","volume":"160","author":"DG Corneil","year":"2012","unstructured":"Corneil, D.G., Habib, M., Lanlignel, J.M., Reed, B., Rotics, U.: Polynomial-time recognition of clique-width 3 graphs. Discrete Appl. Math. 160(6), 834\u2013865 (2012)","journal-title":"Discrete Appl. Math."},{"issue":"2","key":"5_CR7","doi-asserted-by":"crossref","first-page":"218","DOI":"10.1016\/0022-0000(93)90004-G","volume":"46","author":"B Courcelle","year":"1993","unstructured":"Courcelle, B., Engelfriet, J., Rozenberg, G.: Handle-rewriting hypergraph grammars. J. Comput. Syst. Sci. 46(2), 218\u2013270 (1993)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"5_CR8","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1007\/s002249910009","volume":"33","author":"B Courcelle","year":"2000","unstructured":"Courcelle, B., Makowsky, J.A., Rotics, U.: Linear time solvable optimization problems on graphs of bounded clique-width. Theor. Comput. Syst. 33(2), 125\u2013150 (2000)","journal-title":"Theor. Comput. Syst."},{"issue":"1","key":"5_CR9","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1016\/S0166-218X(99)00184-5","volume":"101","author":"B Courcelle","year":"2000","unstructured":"Courcelle, B., Olariu, S.: Upper bounds to the clique width of graphs. Discrete Appl. Math. 101(1), 77\u2013114 (2000)","journal-title":"Discrete Appl. Math."},{"key":"5_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1007\/BFb0017474","volume-title":"Trees in Algebra and Programming \u2014 CAAP\u201994","author":"A Cournier","year":"1994","unstructured":"Cournier, A., Habib, M.: A new linear algorithm for modular decomposition. CAAP\u201994. LNCS, vol. 787, pp. 68\u201384. Springer, Heidelberg (1994)"},{"issue":"3","key":"5_CR11","doi-asserted-by":"crossref","first-page":"734","DOI":"10.4153\/CJM-1980-057-7","volume":"32","author":"WH Cunningham","year":"1980","unstructured":"Cunningham, W.H.: A combinatorial decomposition theory. Can. J. Math. 32(3), 734\u2013765 (1980)","journal-title":"Can. J. Math."},{"issue":"2","key":"5_CR12","doi-asserted-by":"crossref","first-page":"214","DOI":"10.1137\/0603021","volume":"3","author":"WH Cunningham","year":"1982","unstructured":"Cunningham, W.H.: Decomposition of directed graphs. SIAM J. Algebraic Discrete Methods 3(2), 214\u2013228 (1982)","journal-title":"SIAM J. Algebraic Discrete Methods"},{"key":"5_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1007\/978-3-319-15612-5_30","volume-title":"WALCOM: Algorithms and Computation","author":"B Das","year":"2015","unstructured":"Das, B., Enduri, M.K., Reddy, I.V.: Logspace and FPT algorithms for graph isomorphism for subclasses of bounded tree-width graphs. In: Rahman, M.S., Tomita, E. (eds.) WALCOM 2015. LNCS, vol. 8973, pp. 329\u2013334. Springer, Heidelberg (2015)"},{"key":"5_CR14","unstructured":"Das, B., Enduri, M.K., Reddy, I.V.: Polynomial-time algorithm for isomorphism of graphs with clique-width at most 3. arXiv preprint (2015). arXiv:1506.01695"},{"issue":"2","key":"5_CR15","doi-asserted-by":"crossref","first-page":"909","DOI":"10.1137\/070687256","volume":"23","author":"MR Fellows","year":"2009","unstructured":"Fellows, M.R., Rosamond, F.A., Rotics, U., Szeider, S.: Clique-width is NP-complete. SIAM J. Discrete Math. 23(2), 909\u2013939 (2009)","journal-title":"SIAM J. Discrete Math."},{"issue":"1","key":"5_CR16","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 Mathematica Hungarica 18(1), 25\u201366 (1967)","journal-title":"Acta Mathematica Hungarica"},{"key":"5_CR17","doi-asserted-by":"crossref","unstructured":"Grohe, M., Schweitzer, P.: Isomorphism testing for graphs of bounded rank width. In: 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS), pp. 1010\u20131029. IEEE (2015)","DOI":"10.1109\/FOCS.2015.66"},{"key":"5_CR18","unstructured":"James, L.O., Stanton, R.G., Cowan, D.D.: Graph decomposition for undirected graphs. In: Proceedings of 3rd Southeastern Conference on Combinatorics, Graph Theory, and Computing, pp. 281\u2013290 (1972)"},{"issue":"12","key":"5_CR19","doi-asserted-by":"crossref","first-page":"2747","DOI":"10.1016\/j.dam.2008.08.022","volume":"157","author":"M Kami\u0144ski","year":"2009","unstructured":"Kami\u0144ski, M., Lozin, V.V., Milani\u010d, M.: Recent developments on graphs of bounded clique-width. Discrete Appl. Math. 157(12), 2747\u20132761 (2009)","journal-title":"Discrete Appl. Math."},{"key":"5_CR20","doi-asserted-by":"crossref","unstructured":"Lokshtanov, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Fixed-parameter tractable canonization and isomorphism test for graphs of bounded treewidth. In: IEEE 55th Annual Symposium on (FOCS), pp. 186\u2013195 (2014)","DOI":"10.1109\/FOCS.2014.28"},{"issue":"1","key":"5_CR21","doi-asserted-by":"crossref","first-page":"42","DOI":"10.1016\/0022-0000(82)90009-5","volume":"25","author":"EM Luks","year":"1982","unstructured":"Luks, E.M.: Isomorphism of graphs of bounded valence can be tested in polynomial time. J. Comput. Syst. Sci. 25(1), 42\u201365 (1982)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"5_CR22","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1006\/jagm.1994.1007","volume":"16","author":"TH Ma","year":"1994","unstructured":"Ma, T.H., Spinrad, J.: An O( $$n^2$$ ) algorithm for undirected split decomposition. J. Algorithms 16(1), 145\u2013160 (1994)","journal-title":"J. Algorithms"},{"key":"5_CR23","doi-asserted-by":"crossref","unstructured":"Miller, G.: Isomorphism testing for graphs of bounded genus. In: Proceedings of 12th Annual ACM Symposium on Theory of Computing, pp. 225\u2013235. ACM (1980)","DOI":"10.1145\/800141.804670"},{"issue":"4","key":"5_CR24","doi-asserted-by":"crossref","first-page":"514","DOI":"10.1016\/j.jctb.2005.10.006","volume":"96","author":"S Oum","year":"2006","unstructured":"Oum, S., Seymour, P.: Approximating clique-width and branch-width. J. Comb. Theor. Ser. B 96(4), 514\u2013528 (2006)","journal-title":"J. Comb. Theor. Ser. B"},{"issue":"3","key":"5_CR25","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1016\/j.jctb.2006.06.006","volume":"97","author":"S Oum","year":"2007","unstructured":"Oum, S., Seymour, P.: Testing branch-width. J. Comb. Theor. Ser. B 97(3), 385\u2013393 (2007)","journal-title":"J. Comb. Theor. Ser. B"},{"key":"5_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"634","DOI":"10.1007\/978-3-540-70575-8_52","volume-title":"Automata, Languages and Programming","author":"M Tedder","year":"2008","unstructured":"Tedder, M., Corneil, D.G., Habib, M., Paul, C.: Simpler linear-time modular decomposition via recursive factorizing permutations. In: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol. 5125, pp. 634\u2013645. Springer, Heidelberg (2008)"},{"key":"5_CR27","unstructured":"Zemlyachenko, V., Konieko, N., Tyshkevich, R.: Graph isomorphism problem (Russian). In: The Theory of Computation I. Notes Sci. Sem. LOMI, vol. 118 (1982)"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-42634-1_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,6,24]],"date-time":"2017-06-24T14:44:09Z","timestamp":1498315449000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-42634-1_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319426334","9783319426341"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-42634-1_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}