Testing isomorphism of cone graphs(Extended Abstract)

ABSTRACT

We give algorithms to decide graph isomorphism in a subclass of graphs which we call cone graphs. A cone graph is an undirected graph for which there exists a vertex r which uniquely determines a breadth-first search (BFS) tree. Equivalently, all shortest paths from r to any other graph vertex are unique. Our algorithms may be used either nondeterministically or probabilistically. Used as probabilistic algorithms, they return always a correct answer, but with an expected running time only.

REFERENCES

• 1: L. Babai, Monte Carlo Algorithms in Graph Isomorphism Testing, submitted to SIAM J. on Computing (1979)
• 2: J. Hopcroft and R. Tarjan, A VlogV Algorithm for Isomorphism of Triconnected Planar Graphs, J. of Comp. and Sys.Sci. 7(1973) 323–331
• 3: J. E. Hopcroft , J. K. Wong, Linear time algorithm for isomorphism of planar graphs (Preliminary Report), Proceedings of the sixth annual ACM symposium on Theory of computing, p.172-184, April 30-May 02, 1974, Seattle, Washington, United States [doi>10.1145/800119.803896]
• 4: R. Lipton, The Beacon Set Approach to Graph Isomorphism, SIAM J. on Comp. (to appear)
• 5: George S. Lueker , Kellogg S. Booth, A Linear Time Algorithm for Deciding Interval Graph Isomorphism, Journal of the ACM (JACM), v.26 n.2, p.183-195, April 1979 [doi>10.1145/322123.322125]
• 6: Gary L. Miller, On the nlog n isomorphism technique (A Preliminary Report), Proceedings of the tenth annual ACM symposium on Theory of computing, p.51-58, May 01-03, 1978, San Diego, California, United States [doi>10.1145/800133.804331]
• 7: G. Miller, Personal Communication
• 8: M. Hall Jr., The Theory of Groups, -MacMillan, New York 1959
• 9: G. Miller, Isomorphism Testing For Graphs of Bounded Genus, Manuscript (1979)

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

General Terms:
Algorithms, Theory