<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

Data publikacji: 24 wrz 2016

Zakres stron: 163 - 181

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

Słowa kluczowe
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

Data publikacji: 24 wrz 2016

Zakres stron: 163 - 181

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

Słowa kluczowegraph 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.

Słowa kluczowe
graph isomorphism with restriction, partial -trees, polynomial time algorithm