Title
Polynomial Time Algorithms for Variants of Graph Matching on Partial k-Trees
Authors
Year of publication
2016
Published in
Article type
scientific article
Publication language
english
Keywords
EN
- graph isomorphism with restriction
- partial k-trees
- polynomial time algorithm
Abstract
EN 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.
Pages (from - to)
163 - 181
License type
CC BY-NC-ND (attribution - noncommercial - no derivatives)
Full text of article
Access level to full text
public
Ministry points / journal
15
System created by Poznań University of Technology
and Poznan Supercomputing and Networking Center
Log in through eKonto to add to SIS