<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

Published Online: Sep 24, 2016

Page range: 163 - 181

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

Keywords
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

Published Online: Sep 24, 2016

Page range: 163 - 181

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

Keywordsgraph 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.

Keywords
graph isomorphism with restriction, partial -trees, polynomial time algorithm