Isomorphism testing for embeddable graphs through definability

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Isomorphism testing for embeddable graphs through definability

Full text

Pdf (1.04 MB)

Source

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

Portland, Oregon, United States

Pages: 63 - 72

Year of Publication: 2000

ISBN:1-58113-184-4

Author

Martin Grohe

Institut für Mathematische Logik, Eckerstr. 1,79104 Freiburg, Germany

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 38, Citation Count: 2

Additional Information:

references cited by index terms collaborative colleagues peer to peer

Tools and Actions:	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/335305.335313 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.

	1	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
	2	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]
	3	L. Babai, P. ErdSs, and S. Selkow. Random graph isomorphism. SIAM Journal on Computing, 9:628-635, 1980.
	4	L. Babai and L. Kur:era. Canonical labelling of graphs in linear average time. In Proceedings of the 20th Annual IEEE Symposium on Foundations of Computer Science, pages 39-46, 1979.
	5	Hans L. Boblaender, Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees, Journal of Algorithms, v.11 n.4, p.631-643, Dec. 1990 [doi>10.1016/0196-6774(90)90013-5]
	6	R. B. Boppana , J. Hastad , S. Zachos, Does co-NP have short interactive proofs?, Information Processing Letters, v.25 n.2, p.127-132, 6 May 1987 [doi>10.1016/0020-0190(87)90232-8]
	7	J. Cat, M. Fiirer, and N. Immerman. An optimal lower bound on the number of variables for graph identification. Combinatorica, 12:389-410, 1992.
	8	A. Chandra and D. Harel. Structure and complexity of relational queries. Journal of Computer and System Sciences, 25:99-128, 1982.
	9	H.-D. Ebbinghaus and J. Flum. Finite Model Theory. Springer-Verlag, second edition, 1995.
	10	Sergei Evdokimov , Marek Karpinski , Ilia Ponomarenko, On a New High Dimensional Weisfeiler-Lehman Algorithm, Journal of Algebraic Combinatorics: An International Journal, v.10 n.1, p.29-45, July 1999 [doi>10.1023/A:1018672019177 ]
	11	S. Evdokimov and I. Ponomarenko. On highly closed cellular algebras and highly closed isomorphism. Electronic Journal of Combinatorics, 6:~R18, 1999.
	12	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]
	13	M. Grohe. Finite-variable logics in descriptive complexity theory. Bulletin of Symbolic Logic, 4:345-399, 1998.
	14	M. Grohe, Fixed-Point Logics on Planar Graphs, Proceedings of the 13th Annual IEEE Symposium on Logic in Computer Science, p.6, June 21-24, 1998
	15	Martin Grohe , Julian Mariño, Definability and Descriptive Complexity on Databases of Bounded Tree-Width, Proceeding of the 7th International Conference on Database Theory, p.70-82, January 10-12, 1999
	16	C. Hoffmann. Group-theoretic algorithms and graph isomorphism, volume 136 of Lecture Notes in Computer Science. Springer-Verlag, 1982.
	17	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]
	18	J. E. Hopcroft and R. Taxjan. Isomorphism of planar graphs (working paper). In R. E. Miller and J. W. Thatcher, editors, Complexity of Computer Computations. Plenum Press, 1972.
	19	J. E. Hopcroft and R. Tarjan. A vlogv algorithm for isomorphism of triconnected planar graphs. Journal of Computer and System Sciences, 7:323-331, 1973.
	20	N. Immerman. Descriptive Complexity. Springer-Verlag, 1999.
	21	N. Immerman and E. Lander. Describing graphs: A first-order approach to graph canonization. In A. Selman, editor, Complexity theory retrospective, pages 59- 81. Springer-Verlag, 1990.
	22	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]
	23	E. Luks. Isomorphism of graphs of bounded valance can be tested in polynomial time. Journal of Computer and System Sciences, 25:42-65, 1982.
	24	G. Miller. Isomorphism of graphs which are pairwise k-separable. Information and Control, 56:21-33, 1983.
	25	G. Miller. Isomorphism of k-contractible graphs. A generalization of bounded valence and bounded genus. Information and Control, 56:1-20, 1983.
	26	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]
	27	Bojan Mohar, Embedding graphs in an arbitrary surface in linear time, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.392-397, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237986]
	28	I. N. Ponomarenko. The isomorphism problem for classes of graphs that are invariant with respect to contraction. Zap. Nauchn. Sere. Leningrad. Otdel. Mat. Inst. Steklov. (LOMI), 174(Teor. Slozhn. Vychisl. 3):147- 177, 182, 1988. In Russian.
	29	Uwe Schöning, Graph isomorphism is in the low hierarchy, Journal of Computer and System Sciences, v.37 n.3, p.312-323, Dec. 1988 [doi>10.1016/0022-0000(88)90010-4]
	30	W. Tutte. How to draw a graph. Proceedings of the London Mathematical Society, 13:743-768, 1963.

CITED BY 2

	Oleg Pikhurko , Helmut Veith , Oleg Verbitsky, The first order definability of graphs: upper bounds for quantifier depth, Discrete Applied Mathematics, v.154 n.17, p.2511-2529, 15 November 2006
	Oleg Verbitsky, The first order definability of graphs with separators via the Ehrenfeucht game, Theoretical Computer Science, v.343 n.1-2, p.158-176, 10 October 2005