Testing Graph Isomorphism in Parallel by Playing a Game

Details Testing Graph Isomorphism in Parallel by Playing a Game Testing Graph Isomorphism in Parallel by Playing a Game

2006-03-14

arxiv.org/abs/cs/0603054v1

Computer Science

Computational Complexity

21 pages

Scientific paper

Our starting point is the observation that if graphs in a class C have low descriptive complexity in first order logic, then the isomorphism problem for C is solvable by a fast parallel algorithm (essentially, by a simple combinatorial algorithm known as the multidimensional Weisfeiler-Lehman algorithm). Using this approach, we prove that isomorphism of graphs of bounded treewidth is testable in TC1, answering an open question posed by Chandrasekharan. Furthermore, we obtain an AC1 algorithm for testing isomorphism of rotation systems (combinatorial specifications of graph embeddings). The AC1 upper bound was known before, but the fact that this bound can be achieved by the simple Weisfeiler-Lehman algorithm is new. Combined with other known results, it also yields a new AC1 isomorphism algorithm for planar graphs.

Affiliated with

Also associated with

No associations

Rating

Testing Graph Isomorphism in Parallel by Playing a Game does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Testing Graph Isomorphism in Parallel by Playing a Game, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Testing Graph Isomorphism in Parallel by Playing a Game will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-704662