<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

Pubblicato online: 24 set 2016

Pagine: 163 - 181

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

Parole chiave
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

Pubblicato online: 24 set 2016

Pagine: 163 - 181

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

Parole chiavegraph 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.

Parole chiave
graph isomorphism with restriction, partial -trees, polynomial time algorithm