In this paper, we study the following problem: given two graphs G and H and an isomorphism Φ between an induced subgraph of G and an induced subgraph of H, compute the number of isomorphisms between G and H that doesn't contradict to Φ. We show that this problem can be solved in O((k + 1)！n{sup}3) time when input graphs are restricted to chordal graphs with clique number at most k + 1. To show this, we first show that the tree model of a chordal graph can be uniquely constructed except for the ordering of children of each node in O(n{sup}3) time. Then, we show that the number of isomorphisms between G and H that doesn't contradict to Φ can be efficiently computed by use of the tree model.
展开▼
