IEICE Trans - Computing Automorphism Groups of Chordal Graphs Whose Simplicial Components Are of Small Size

Computing Automorphism Groups of Chordal Graphs Whose Simplicial Components Are of Small Size

Seinosuke TODA

Publication
IEICE TRANSACTIONS on Information and Systems Vol.E89-D No.8 pp.2388-2401
Publication Date: 2006/08/01
Online ISSN: 1745-1361
DOI: 10.1093/ietisy/e89-d.8.2388
Print ISSN: 0916-8532
Type of Manuscript: Special Section INVITED PAPER (Special Section on Invited Papers from New Horizons in Computing)
Category:
Keyword:
chordal graph, simplicial component, automorphism, isomorphism, computational group theory, algorithm, computational complexity,

Full Text: PDF(290.1KB)>>

Summary:
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.

open access publishing via