Computing Automorphism Groups of Chordal Graphs Whose Simplicial Components Are of Small Size(<Special Section>Invited Papers from New Horizons in Computing)

スポンサーリンク

概要

• 論文の詳細を見る

• 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.

• 社団法人電子情報通信学会の論文
• 2006-08-01

著者

• Toda Seinosuke

  Department Of Computer Science And System Analysis College Of Humanities And Sciences Nihon Universi

関連論文

• The Complexity of Selecting Maximal Solutions
• Grammatical Characterizations of P and PSPACE
• Computing Automorphism Groups of Chordal Graphs Whose Simplicial Components Are of Small Size(Invited Papers from New Horizons in Computing)
• A Note on the Length of M-Programs over Nonsolvable Groups

スポンサーリンク