Polynomial Time Algorithms for Variants of Graph Matching on Partial k-Trees
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.
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.