Polynomial Time Algorithms for Variants of Graph Matching on Partial k -Trees
| 24. Sept. 2016
Über diesen Artikel
Online veröffentlicht: 24. Sept. 2016
Seitenbereich: 163 - 181
DOI: https://doi.org/10.1515/fcds-2016-0010
Schlüsselwörter
© 2016 Takayuki Nagoya, published by De Gruyter Open
This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.
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