Faster isomorphism testing of strongly regular graphs

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Faster isomorphism testing of strongly regular graphs

Full text

Pdf (799 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-eighth annual ACM symposium on Theory of computing table of contents

Philadelphia, Pennsylvania, United States

Pages: 576 - 584

Year of Publication: 1996

ISBN:0-89791-785-5

Author

Daniel A. Spielman

Computer Science Division, U.C. Berkeley, CA

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 8, Downloads (12 Months): 59, Citation Count: 4

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/237814.238006 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	Bab79	L~iszl6 Babai. Monte Carlo algorithms in graph isomorphism testing. Technical Report 79-10, Ddp. Math et $tat., Univ. de Montreal, 1979.
	Bab80	L~szl6 Bahai. On the complexity of canonical labeling of strongly regular graphs. SIAM J. Comput., 9(1):212-216, 1980.
	Bab81a	László Babai, Moderately Exponential Bound for Graph Isomorphism, Proceedings of the 1981 International FCT-Conference on Fundamentals of Computation Theory, p.34-50, August 24-28, 1981
	Bab81b	L~tszl6 Babai. On the order of uniprimitive permuation groups. Annals of Mathematics, 113:553-568, 1981.
	BGM82	László Babai , D. Yu. Grigoryev , David M. Mount, Isomorphism of graphs with bounded eigenvalue multiplicity, Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.310-324, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802206]
	BK79	L~tszl6 Babai and Ludik Ku~era. Canonical labelling of graphs in linear average time. In Proceedzngs of the 1920th IEEE Symposium on Foundations of Computer Science, pages 39-46, 1979.
	BL83	László Babai , Eugene M. Luks, Canonical labeling of graphs, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.171-183, December 1983 [doi>10.1145/800061.808746]
	Bos63	R.C. Bose. Strongly regular graphs, partial geometries and partially balanced designs. Pacific J. Math., 13:389-419, 1963.
	Cam78	P.J. Cameron. Strongly regular graphs. In Selected Topics in Graph Theory, pages 337- 380. Academic Press, London, 1978.
	CFI92	Jin-Yi Cai, Martin Fiirer, and Neil Immerman. An optimal lower bound on the number of variables for graph identification. Combinatorica, 12(4):389-410, 1992.
	CGW89	F.R.K. Chung, R.L. Graham, and R.M. Wilson. Quasi-random graphs. Combinatorica, 9(4):345-362, 1989.
	FM80	I. S. Filotti , Jack N. Mayer, A polynomial-time algorithm for determining the isomorphism of graphs of fixed genus, Proceedings of the twelfth annual ACM symposium on Theory of computing, p.236-243, April 28-30, 1980, Los Angeles, California, United States [doi>10.1145/800141.804671]
	Kuc87	Lud~k Ku~era. Canonical labeling of regular graphs in linear average time. In Proceedings of the ~8th IEEE Symposium on Foundations of Computer Science, pages 271-279, 1987.
	Lic80	David Lichtenstein, Isomorphism for graphs embeddable on the projective plane, Proceedings of the twelfth annual ACM symposium on Theory of computing, p.218-224, April 28-30, 1980, Los Angeles, California, United States [doi>10.1145/800141.804669]
	Luk82	Eugene M. Luks. isomorphism of graphs of bounded valence can be tested in polynomial time. Journal of Computer and System Sciences, 25:42-65, 1982.
	Mil78	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]
	Mil80	Gary Miller, Isomorphism testing for graphs of bounded genus, Proceedings of the twelfth annual ACM symposium on Theory of computing, p.225-235, April 28-30, 1980, Los Angeles, California, United States [doi>10.1145/800141.804670]
	Mil83	Gary L. Miller. Isomorphism of k-contractible graphs, a generalization of bounded valence and bounded genus. Information and Control, 56:1-20, 1983.
	Moh89	B. Mohar, Isoperimetric numbers of graphs, Journal of Combinatorial Theory Series B, v.47 n.3, p.274-291, Dec. 1989 [doi>10.1016/0095-8956(89)90029-4]
	Neu79	A. Neumaier. Stronly regular graphs with smallest eigenvalue -m. Arch. Math., 33:392-400, 1979.
	Pon89	Ilja N. Ponomarenko. The isomorphismproblem for classes of graphs. Soviet Math. Dokl., 39:119-122, 1989.
	RC77	R.C. Read and D. G. Corneil. The graph isomorphism disease. J. Graph Theory, 1:339- 363, 1977.
	Sei79	J.J. Seidel. Strongly regular graphs. In B. Bollob~ts, editor, Surveys in Combinatorics, volume 38 of London Mathematical Society Lecture Note Serzes, pages 157-180. Cambridge University Press, 1979.
	SJ89	Alistair Sinclair , Mark Jerrum, Approximate counting, uniform generation and rapidly mixing Markov chains, Information and Computation, v.82 n.1, p.93-133, July 1989 [doi>10.1016/0890-5401(89)90067-9]
	vLW92	J.H. van Lint and R. M. Wilson. A Course in Combinatorica. Cambridge University Press, 1992.
	ZKT85	V. M. Zemlyachenko, N. M. Kornienko, and R. I. Tyshkevich. Graph isomorphism problem. Journal of Soviet Mathematics, 29:1426- 1481, 1985.

CITED BY 4

	Eugene M. Luks, Hypergraph isomorphism and structural equivalence of Boolean functions, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.652-658, May 01-04, 1999, Atlanta, Georgia, United States
	Cristopher Moore , Alexander Russell , Piotr Sniady, On the impossibility of a quantum sieve algorithm for graph isomorphism, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA
	David Emms , Simone Severini , Richard C. Wilson , Edwin R. Hancock, Coined quantum walks lift the cospectrality of graphs and trees, Pattern Recognition, v.42 n.9, p.1988-2002, September, 2009
	Sergei Evdokimov , Ilia Ponomarenko, Permutation group approach to association schemes, European Journal of Combinatorics, v.30 n.6, p.1456-1476, August, 2009