Polynomial Time Algorithms for Variants of Graph Matching on Partial k-Trees
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 prob...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Sciendo
2016-09-01
|
| Series: | Foundations of Computing and Decision Sciences |
| Subjects: | |
| Online Access: | https://doi.org/10.1515/fcds-2016-0010 |