1. bookVolume 41 (2016): Issue 3 (September 2016)
Journal Details
License
Format
Journal
eISSN
2300-3405
First Published
24 Oct 2012
Publication timeframe
4 times per year
Languages
English
access type Open Access

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

Published Online: 24 Sep 2016
Volume & Issue: Volume 41 (2016) - Issue 3 (September 2016)
Page range: 163 - 181
Journal Details
License
Format
Journal
eISSN
2300-3405
First Published
24 Oct 2012
Publication timeframe
4 times per year
Languages
English
Abstract

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.

Keywords

[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 n5/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(n5/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

Recommended articles from Trend MD

Plan your remote conference with Sciendo