A dynamic programming algorithm for the tree mapping problem |
| |
| Affiliation: | Division of Clinical Epidemiology, Geneva University Hospitals, and Faculty of Medicine, University of Geneva, Geneva 1211, Switzerland |
| |
| Abstract: | In the graph mapping problem two graphs and a cost function are given as input and the goal is to find a minimum cost mapping of the vertex set of one graph into the vertex set of the other graph. In this paper we introduce a dynamic programming algorithm for the tree mapping problem (i.e., the variant of the problem in which the input graphs are trees), which is still NP-hard, and evaluate its performance with computational experiments. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
