Polynomial Time Algorithms for Variants of Graph Matching on Partial k-Trees

[1] Arnborg S., Corneil D., and Proskurowski A., Complexity of finding embeddings in a k-tree, SIAM J. Alg. Disc. Meth., 8, 1987, 277–284.10.1137/0608024Search in Google Scholar

[2] Babel L., Ponomarenko I. N. and Tinhofer G., The Isomorphism Problems for directed Path Graphs and for Rooted Directed Path Graphs, J. Algorithms, 21, 1996, 542–564.10.1006/jagm.1996.0058Search in Google Scholar

[3] Bodlaender H. L., Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees, J. Algorithms, 11, 1990, 631–643.10.1016/0196-6774(90)90013-5Search in Google Scholar

[4] Booth K. S. and Colbourn C. J., Problems polynomially equivalent to graph isomorphism, Technical Report CS-77-04, Computer Science Department, University of Waterloo, 1979Search in Google Scholar

[5] Brandstädt A., Le V. B. and Spinrad J. P., Graph Classeses: A Survey, SIAM, 1999.10.1137/1.9780898719796Search in Google Scholar

[6] Colbourn G.J., On testing isomorphism of permutation graphs, Networks, 11, 1981, 13–21.10.1002/net.3230110103Search in Google Scholar

[7] Hopcroft J. and Karp R. M., An n^5/2 algorithm for maximum matching in bipartite graphs, SIAM J. Comput., 4, 1975, 225–231.10.1137/0202019Search in Google Scholar

[8] Köbler J. and Schöning U. and ToranJ., The Graph Isomorphism Problem: Its Structural Complexity, Birkhauser, 1993.10.1007/978-1-4612-0333-9Search in Google Scholar

[9] Lee J., Han W. S., Kasperovics R., and Lee J. H., An indepth comparison of subgraph isomorphism algorithms in graph databases, Proceedings of the 39th international conference on Very Large Data Bases. VLDB Endowment, 2012, 133–144.10.14778/2535568.2448946Search in Google Scholar

[10] Lubiw A., Some NP-complete problems similar to graph isomorphism, SIAM J. Comput., 10(1), 1981, 11–21.10.1137/0210002Search in Google Scholar

[11] Lueker G. S. and Booth K. S., A Linear Time Algorithm for deciding interval graph isomorphism, J. ACM, 26, 1979, 183–195.10.1145/322123.322125Search in Google Scholar

[12] Matura D., Subtree isomorphism in O(n^5/2), Annals of Discrete Mathematics, 2, 1978, 91–106.10.1016/S0167-5060(08)70324-8Search in Google Scholar

[13] Nagoya T., Algorithms for Graph Isomorphism with Restriction on Chordal Graphs with Bounded Clique Size, IEICE Trans. Inf. & Sys., J95-D(11), 2012, 1889–1896.Search in Google Scholar

[14] Nagoya T. and Toda S., Computational Complexity of Computing a Partial Solution for the Graph Automorphism Problems, Theor. Comput. Sci., 410, 2009, 2064–2071.10.1016/j.tcs.2009.01.001Search in Google Scholar

[15] Saltz M., Jain A., Kothari A., Fard A., Miller J. A., Ramaswamy L., An Algorithm for Subgraph Pattern Matching on Very Large Labeled Graphs, IEEE International Congress on Big Data, 2014.10.1109/BigData.Congress.2014.79Search in Google Scholar

[16] Toda S., Computing Automorphism Groups of Chordal Graphs Whose Simplicial Components Are of Small Size, IEICE Trans. Inf. & Sys., E89-D(8), 2006, 2388–2401.10.1093/ietisy/e89-d.8.2388Search in Google Scholar

[17] Uehara R. and Uno Y., Laminar Structure of Ptolemaic Graphs with Applications. Disc. Appl. Math., 157, 2009, 1533–1543.10.1016/j.dam.2008.09.006Search in Google Scholar