Polynomial Time Algorithms for Variants of Graph Matching on Partial k-Trees
References
- [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/0608024
- [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.0058
- [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-5
- [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, 1979
- [5] Brandstädt A., Le V. B. and Spinrad J. P., Graph Classeses: A Survey, SIAM, 1999.10.1137/1.9780898719796
- [6] Colbourn G.J., On testing isomorphism of permutation graphs, Networks, 11, 1981, 13–21.10.1002/net.3230110103
- [7] Hopcroft J. and Karp R. M., An n5/2 algorithm for maximum matching in bipartite graphs, SIAM J. Comput., 4, 1975, 225–231.10.1137/0202019
- [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-9
- [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.2448946
- [10] Lubiw A., Some NP-complete problems similar to graph isomorphism, SIAM J. Comput., 10(1), 1981, 11–21.10.1137/0210002
- [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.322125
- [12] Matura D., Subtree isomorphism in O(n5/2), Annals of Discrete Mathematics, 2, 1978, 91–106.10.1016/S0167-5060(08)70324-8
- [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.
- [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.001
- [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.79
- [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.2388
- [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.006
Language: English
Page range: 163 - 181
Published on: Sep 24, 2016
Published by: Poznan University of Technology
In partnership with: Paradigm Publishing Services
Publication frequency: 4 times per year
Related subjects:
© 2016 Takayuki Nagoya, published by Poznan University of Technology
This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.