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

• Autorzy: Nagoya, T.
• Języki publikacji: EN

Abstrakty

EN

In this paper, we deal with two variants of graph matching, the graph isomorphism with restriction and the prefix set of graph isomorphism. The former problem is known to be NP-complete, whereas the latter problem is known to be GI-complete. We propose polynomial time exact algorithms for these problems on partial k-trees.

Słowa kluczowe

EN

graph isomorphism with restriction; partial k-trees; polynomial time algorithm

• Czasopismo: Foundations of Computing and Decision Sciences
• Rocznik: 2016
• Tom: Vol. 41, No. 3
• Strony: 163--181
• Opis fizyczny: Bibliogr. 17 poz., fig.

Twórcy

autor

Nagoya, T.

• Tottori University of Environmental Studies, 1-1-1 Wakabadai-Kita, Tottori, Tottori 689-1111, Japan,

Bibliografia

• [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.
• [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.
• [3] Bodlaender H.L., Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees, J. Algorithms, 11, 1990, 631–643.
• [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.
• [6] Colbourn G.J., On testing isomorphism of permutation graphs, Networks, 11, 1981, 13–21.
• [7] Hopcroft J. and Karp R.M., An n5/2 algorithm for maximum matching in bipartite graphs, SIAM J. Comput., 4, 1975, 225–231.
• [8] Köbler J. and Schöning U. and Toran J., The Graph Isomorphism Problem: Its Structural Complexity, Birkhauser, 1993.
• [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] Lubiw A., Some NP-complete problems similar to graph isomorphism, SIAM J. Comput., 10(1), 1981, 11–21.
• [11] Lueker G.S. and Booth K.S., A Linear Time Algorithm for deciding interval graph isomorphism, J. ACM, 26, 1979, 183–195.
• [12] Matura D., Subtree isomorphism in O(n5/2), Annals of Discrete Mathematics, 2, 1978, 91–106.
• [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.
• [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.
• [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.
• [17] Uehara R. and Uno Y., Laminar Structure of Ptolemaic Graphs with Applications. Disc. Appl. Math., 157, 2009, 1533–1543.

Uwagi

This is an extended version of the paper presented at the International Conference on Big Data Intelligence and Computing (DataCom 2015), Chengdu, China, December 19-21, 2015.

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę.

Identyfikatory

DOI

10.1515/fcds-2016-0010