article

Free access

An O(n³log n) deterministic and an O(n³) Las Vegs isomorphism test for trivalent graphs

Authors:

Zvi Galil,

Christoph M. Hoffmann,

Eugene M. Luks,

Claus P. Schnorr,

Andreas WeberAuthors Info & Claims

Journal of the ACM (JACM), Volume 34, Issue 3

Pages 513 - 531

https://doi.org/10.1145/28869.28870

Published: 01 July 1987 Publication History

PDF eReader

Abstract

This paper describes an O(n³logn) deterministic algorithm and an O(n³) Las Vegas algorithm for testing whether two given trivalent graphs on n vertices are isomorphic. In fact, the algorithms construct the set of all isomorphisms between two such graphs, presenting, in particular, generators for the group of all automorphisms of a trivalent graph. The algorithms are based upon the original polynomial-time solution to these problems by Luks but they introduce numerous speedups. These include improved permutation-group algorithms that exploit the structure of the underlying 2-groups. A remarkable property of the Las Vegas algorithm is that it computes the set of all isomorphisms between two trivalent graphs for the cost of computing only those isomorphisms that map a specified edge to a specified edge.

References

[1]

AHO, A. V., HOPCROFr, J. E., AND ULLMAN, J. D. The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, Mass., 1974.

Crossref

Google Scholar

[2]

BAnAl, L. Monte-Carlo algorithms in graph isomorphism testing. Tech. Rep., Univ. of Montreal, Montreal, Ontario, Canada, 1979.

Google Scholar

[3]

BAnAl, L., AND LOV.&SZ, L. Permutation groups and almost regular graphs. Studia Sci. Math. Hung. 8 (1973), 141-150.

Google Scholar

[4]

FURST, M., HOPCROFT, J., AND LUKS, E. A subexponential algorithm for trivalent graph isomorphism. Tech. Rep. 80-426, Dept. of Computer Science, Cornell Univ., Ithaca, N.Y., 1980.

Crossref

Google Scholar

[5]

FURST, M., HOPCROFT, J., AND LUKS, E. Polynomial-time algorithms for permutation groups. In Proceedings of the 21st IEEE Symposium on Foundations of Computer Science. IEEE, New York, 1980, pp. 36-41.

Google Scholar

[6]

HALL, M. The Theory of Groups. Macmillan, New York, 1959.

Google Scholar

[7]

HOFFMANN, C.M. An O(n4) isomorphism test for trivalent graphs. Manuscript, August 1981.

Google Scholar

[8]

LUKS, E.M. Isomorphism of graphs of bounded valence can be tested in polynomial time. In Proceedings of the 21st IEEE Symposium on Foundations of Computer Science. IEEE, New York, 1980, pp. 42-49.

Google Scholar

[9]

LUKS, E. M. Isomorphism of graphs of bounded valence can be tested in polynomial time. J. Comput. Syst. Sci. 25 (1982), 42-65.

Google Scholar

[10]

MILLER, G.L. Graph isomorphism, general remarks. J. Comput. Syst. Sci. 18 (1979), 128-142.

Google Scholar

[11]

SCHNORR, C. P., AND WEBER, A. Constructing the automorphism group Auto(X) for trivalent graphs in time O(n31ogn). Tech. Rep., Univ. of Frankfurt, Frankfurt, West Germany, Nov. 1981.

Google Scholar

[12]

TARJAN, R.E. Efficiency of a good but not linear set union algorithm. J. ACM 22, 2 (Apr. 1975), 215-225.

Crossref

Google Scholar

[13]

TuTrE, W.T. A family of cubical graphs. Proc. Cambridge Phil. Soc. 43 (1947), 459-474.

Google Scholar

Cited By

View all

Gu GNam YPark KGalil ZItaliano GHan W(2021)Scalable Graph Isomorphism: Combining Pairwise Color Refinement and Backtracking via Compressed Candidate Space2021 IEEE 37th International Conference on Data Engineering (ICDE)10.1109/ICDE51399.2021.00122(1368-1379)Online publication date: Apr-2021
https://doi.org/10.1109/ICDE51399.2021.00122
Kruglov VMalyshev DPochinka O(2019)On Algorithms that Effectively Distinguish Gradient-Like Dynamics on SurfacesArnold Mathematical Journal10.1007/s40598-019-00103-0Online publication date: 15-Mar-2019
https://doi.org/10.1007/s40598-019-00103-0
Grines VMalyshev DPochinka OZinina S(2016)Efficient algorithms for the recognition of topologically conjugate gradient-like diffeomorhismsRegular and Chaotic Dynamics10.1134/S156035471602004021:2(189-203)Online publication date: 13-Apr-2016
https://doi.org/10.1134/S1560354716020040
Show More Cited By

Index Terms

An O(n³log n) deterministic and an O(n³) Las Vegs isomorphism test for trivalent graphs
1. Mathematics of computing
  1. Discrete mathematics
2. Theory of computation
  1. Randomness, geometry and discrete structures

Recommendations

An O(n3 log n) deterministic and an O (n 3) probabilistic isomorphism test for trivalent graphs
SFCS '82: Proceedings of the 23rd Annual Symposium on Foundations of Computer Science

The main results of this paper are an O(n3) probabilistic algorithm and an O(n3 log n) deterministic algorithm that test whether two given trivalent graphs are isomorphic. In fact, the algorithms construct the set of all isomorphisms of the two graphs. ...
Isomorphism between Cayley (di)graphs

Let @C and @D be finite groups. We give a sufficient condition to prove that every Cayley graph of @C is isomorphic to a Cayley graph of @D. As an application of this result, it is proved that every Cayley graph of a certain group of order 12 is ...
Isomorphism criterion for monomial graphs

Let q be a prime power, 𝔽_q be the field of q elements, and k, m be positive integers. A bipartite graph G = G_q(k, m) is defined as follows. The vertex set of G is a union of two copies P and L of two-dimensional vector spaces over 𝔽_q, with two ...

Comments

Information & Contributors

Information

Published In

Journal of the ACM Volume 34, Issue 3

July 1987

248 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/28869

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 1987

Published in JACM Volume 34, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

17
Total Citations
View Citations
559
Total Downloads

Downloads (Last 12 months)41
Downloads (Last 6 weeks)11

Reflects downloads up to 26 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Gu GNam YPark KGalil ZItaliano GHan W(2021)Scalable Graph Isomorphism: Combining Pairwise Color Refinement and Backtracking via Compressed Candidate Space2021 IEEE 37th International Conference on Data Engineering (ICDE)10.1109/ICDE51399.2021.00122(1368-1379)Online publication date: Apr-2021
https://doi.org/10.1109/ICDE51399.2021.00122
Kruglov VMalyshev DPochinka O(2019)On Algorithms that Effectively Distinguish Gradient-Like Dynamics on SurfacesArnold Mathematical Journal10.1007/s40598-019-00103-0Online publication date: 15-Mar-2019
https://doi.org/10.1007/s40598-019-00103-0
Grines VMalyshev DPochinka OZinina S(2016)Efficient algorithms for the recognition of topologically conjugate gradient-like diffeomorhismsRegular and Chaotic Dynamics10.1134/S156035471602004021:2(189-203)Online publication date: 13-Apr-2016
https://doi.org/10.1134/S1560354716020040
Hsieh SHsu CTi YKuo C(2014)Reducing the bottleneck of graph-based data mining by improving the efficiency of labeled graph isomorphism testingData & Knowledge Engineering10.1016/j.datak.2014.02.00391(17-33)Online publication date: May-2014
https://doi.org/10.1016/j.datak.2014.02.003
Ori OCataldo FVukičević DGraovac A(2010)Topological Determination of 13C–NMR Spectra of C66 FullerenesThe Mathematics and Topology of Fullerenes10.1007/978-94-007-0221-9_11(205-216)Online publication date: 28-Dec-2010
https://doi.org/10.1007/978-94-007-0221-9_11
Boros EGurvich VZverovich I(2008)Neighborhood hypergraphs of bipartite graphsJournal of Graph Theory10.1002/jgt.2029358:1(69-95)Online publication date: 21-Jan-2008
https://doi.org/10.1002/jgt.20293
Fukuda KNakamori M(2003)Graph Isomorphism Algorithm by Perfect MatchingSystem Modeling and Optimization XX10.1007/978-0-387-35699-0_12(229-238)Online publication date: 2003
https://doi.org/10.1007/978-0-387-35699-0_12
Campbell SKumar MBunke H(2001)Parallel subgraph matching on a hierarchical interconnection networkHardware implementation of intelligent systems10.5555/570780.570789(245-275)Online publication date: 1-Jan-2001
https://dl.acm.org/doi/10.5555/570780.570789
Campbell SKumar MBunke H(2001)Parallel Subgraph Matching on a Hierarchical Interconnection NetworkHardware Implementation of Intelligent Systems10.1007/978-3-7908-1816-1_9(245-275)Online publication date: 2001
https://doi.org/10.1007/978-3-7908-1816-1_9
Luks EVitter JLarmore LLeighton T(1999)Hypergraph isomorphism and structural equivalence of Boolean functionsProceedings of the thirty-first annual ACM symposium on Theory of Computing10.1145/301250.301427(652-658)Online publication date: 1-May-1999
https://dl.acm.org/doi/10.1145/301250.301427
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Index Terms

Recommendations

An O(n3 log n) deterministic and an O (n 3) probabilistic isomorphism test for trivalent graphs

Isomorphism between Cayley (di)graphs

Isomorphism criterion for monomial graphs

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations