The search functionality is under construction.

Author Search Result

[Author] Takayuki NAGOYA(1hit)

1-1hit
  • Counting Graph Isomorphisms among Chordal Graphs with Restricted Clique Number

    Takayuki NAGOYA  

     
    PAPER-Algorithms

      Vol:
    E85-D No:7
      Page(s):
    1065-1073

    In this paper, we study the following problem: given two graphs G, 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 do not contradict φ. We show that this problem can be solved in O(((k+1)(k+1)!)2n3) time when the input graphs are restricted to chordal graphs with clique number at most k+1. To prove this, we first show that the tree model of a chordal graph can be uniquely constructed in O(n3) time except for the ordering of children of each node. Then, we show that the number of φ-isomorphisms between G and H can be efficiently computed by use of the tree model.