<abstract xmlns="http://www.w3.org/1999/xhtml"><p>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 <italic>k</italic>-trees.</p></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.

Polynomial Time Algorithms for Variants of Graph Matching on Partial <italic>k</italic>-Trees

Tottori University of Environmental Studies, 1-1-1 Wakabadai-Kita, Tottori, Tottori 689-1111,

Foundations of Computing and Decision Sciences

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

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

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

Publié en ligne: 24 sept. 2016

Pages: 163 - 181

DOI: https://doi.org/10.1515/fcds-2016-0010

Mots clés
graph isomorphism with restriction, partial -trees, polynomial time algorithm

© 2016 Takayuki Nagoya, published by De Gruyter Open

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

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

Publié en ligne: 24 sept. 2016

Pages: 163 - 181

DOI: https://doi.org/10.1515/fcds-2016-0010

Mots clésgraph isomorphism with restriction, partial -trees, polynomial time algorithm

© 2016 Takayuki Nagoya, published by De Gruyter Open

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

Mots clés
graph isomorphism with restriction, partial -trees, polynomial time algorithm