<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

Publicado en línea: 24 sept 2016

Páginas: 163 - 181

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

Palabras clave
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

Publicado en línea: 24 sept 2016

Páginas: 163 - 181

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

Palabras clavegraph 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.

Palabras clave
graph isomorphism with restriction, partial -trees, polynomial time algorithm