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 |
| _version_ | 1818486168135663616 |
|---|---|
| author | Nagoya Takayuki |
| author_facet | Nagoya Takayuki |
| author_sort | Nagoya Takayuki |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-12-10T16:19:17Z |
| format | Article |
| id | doaj.art-a3720285892e4bf7856495ac9eb0eca4 |
| institution | Directory Open Access Journal |
| issn | 2300-3405 |
| language | English |
| last_indexed | 2024-12-10T16:19:17Z |
| publishDate | 2016-09-01 |
| publisher | Sciendo |
| record_format | Article |
| series | Foundations of Computing and Decision Sciences |
| spelling | doaj.art-a3720285892e4bf7856495ac9eb0eca42022-12-22T01:41:52ZengSciendoFoundations of Computing and Decision Sciences2300-34052016-09-0141316318110.1515/fcds-2016-0010fcds-2016-0010Polynomial Time Algorithms for Variants of Graph Matching on Partial k-TreesNagoya Takayuki0Tottori University of Environmental Studies, 1-1-1 Wakabadai-Kita, Tottori, Tottori 689-1111, JapanIn 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.https://doi.org/10.1515/fcds-2016-0010graph isomorphism with restrictionpartial k-treespolynomial time algorithm |
| spellingShingle | Nagoya Takayuki Polynomial Time Algorithms for Variants of Graph Matching on Partial k-Trees Foundations of Computing and Decision Sciences graph isomorphism with restriction partial k-trees polynomial time algorithm |
| title | Polynomial Time Algorithms for Variants of Graph Matching on Partial k-Trees |
| title_full | Polynomial Time Algorithms for Variants of Graph Matching on Partial k-Trees |
| title_fullStr | Polynomial Time Algorithms for Variants of Graph Matching on Partial k-Trees |
| title_full_unstemmed | Polynomial Time Algorithms for Variants of Graph Matching on Partial k-Trees |
| title_short | Polynomial Time Algorithms for Variants of Graph Matching on Partial k-Trees |
| title_sort | polynomial time algorithms for variants of graph matching on partial k trees |
| topic | graph isomorphism with restriction partial k-trees polynomial time algorithm |
| url | https://doi.org/10.1515/fcds-2016-0010 |
| work_keys_str_mv | AT nagoyatakayuki polynomialtimealgorithmsforvariantsofgraphmatchingonpartialktrees |