Computing Automorphism Groups of Chordal Graphs Whose Simplicial Components Are of Small Size
S. TODA · IEICE Transactions on Information and Systems · 2006
It is known that any chordal graph can be uniquely decomposed into simplicial components. Based on this fact, it is shown that for a given chordal graph, its automorphism group can be computed in O((c! · n)O(1)) time, where c denotes the maximum size of simplicial components and n denotes the number of nodes. It is also shown that isomorphism of those chordal graphs can be decided within the same time bound. From the viewpoint of polynomial-time computability, our result strictly strengthens the previous ones respecting the clique number.