More Web Proxy on the site http://driver.im/

article

Free access

A Fast Backtracking Algorithm to Test Directed Graphs for Isomorphism Using Distance Matrices

Authors:

Douglas C. Schmidt,

Larry E. DruffelAuthors Info & Claims

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

Pages 433 - 445

https://doi.org/10.1145/321958.321963

Published: 01 July 1976 Publication History

Abstract

A backtracking algorithm for testing a pair of digraphs for isomorphism is presented. The information contained in the distance matrix representation of a graph is used to establish an initial partition of the graph's vertices. This distance matrix information is then applied in a backtracking procedure to reduce the search tree of possible mappings. While the algorithm is not guaranteed to run in polynomial time, it performs efficiently for a large class of graphs.

References

[1]

HARARY, F. The determinant of the adjacency matrix of a graph SIAM Rev 4, 3 (July 1962), 202- 210

[2]

TURNER, J Generalized matrix functions and the graph Isomorphism problem SIAM J Appl Math 16, 3 (May 1968), 520-526

[3]

KAae, R M Reducibility among combinatorial problems Tech. Rep #3, Comput Sc} Dep, U of Cahforma, Berkeley, Cahf, April 1972

[4]

UN(;En, S H GIT-A heuristic program for testmg pairs of directed line graphs for Isomorphism Comm. ACM 7, 1 (Jan 1964), 26-34

[5]

SUSSENGUTH JR, E H A graph-theoretic algorithm for matching chemical structures J Chem Doc 5, 1 (1965), 36-43

[6]

SAUCIER, G Un Algorithme Efficace Recherchant rlsmorphisme de 2 Graphes Rev Franca~se Informat Recherche Operatmnelle 5 (1971), 39-51

[7]

STEEN, J P Princlpe d'un Algorithm de Recherche d'un Isomorphisme entre Deux Graphes Rev Franca~se Informat Recherche Operatmnelle 3 (1969), 51-69

[8]

SHAH, Y J, DAVIDA, G I, AND MCCARTHY, M K Optimum features and graph Isomorphism Trans on Systems, Man, and Cybernetics SMC-4, 3 (May 1974), 313-319

[9]

BERZTISS, A T A backtrack procedure for isomorphism of directed graphs J ACM 20, 3 (July 1973), 365-377

[10]

CORNEIL, D G, AN}) GOTLIEB, C C An efficient algorithm for graph Isomorphism J ACM 17, 1 (Jan 1970), 51-64

[11]

CORNEIL, D G Graph Isomorphism Ph D Diss, Dep of Comput Sci, U of Toronto, Toronto, Ontario, Canada, 1968

[12]

CORNEIL, D G. The analysm of graph theoretic algomthms Tech Rep #65, Dep ofComput Scl, U of Toronto, Toronto, Ontario, Canada, 1974

[13]

HOPCROFT, J E, AND TARJAN, R E. Isomorphism of planar graphs In Complexity of Computer Computations, R E Miller and J W Thatcher, Eds, Plenum Press, New York, 1972, pp 143-150

[14]

HOPCROFT, J E, AND WONG, J K Linear time algorithm for isomorphism of planar graphs Proc of the 6th Annual ACM Syrup on the Theory of Computing, Seattle, Wash, April 30, 1974, pp. 172- 184

[15]

WmNBERG, L A simple and efficient algorithm for determining momorphlsm of planar triply connected graphs IEEE Trans on C~rcu~t Theory CT-I3 (1966), 142-148

[16]

BEHZAD, M, AND CHARTRAND, G Introduction to the Theory of Graphs Allyn and Bacon, Boston, 1971

[17]

HAKIMr, S L, AND YAU, S S Distance matrix of a graph and its rehablhty Quart of Appl Math XXII, 4 (1965), 305-317

[18]

DREYFUS, S E An appraisal of some shortest distance algorithms Oper Res 17 (1969), 395-412

[19]

FLOYD, R W Algorithm 97, Shortest path Comm ACM 5, 6 (June 1962), 345

[20]

ULAM, S M A Collectzon of Mathematical Problems Wiley, New York, 1960.

[21]

TURNER, J Pomt-symmetmc graphs with a prime number of points J Comb. Theor 3 (1967), 136- 145

[22]

HOFFMAN, A J Private communication

[23]

BosE, R C Strongly regular graphs, partml geometries and partially balanced designs Pacific J Math. 13 (1963), 389-420.

[24]

PAULUS, A.J L. Conferevce matrices and graphs of order 26. Tech Rep 73-WSK-06, Technologmal U Eindhoven, Nether~ar, ds, 1973

[25]

CORNEXL, D G Private communicatmn

[26]

BUSSEMAKER, F.C, AND SEIDEL, J J Symmetric Hadamard matrices of order 36 Tech. Rep. 70- WSK-02, Technological U Eindhoven, Netherlands, 1970

Cited By

Tian YCarballo ALi RTakeda K(2023)RSG-Search: Semantic Traffic Scene Retrieval Using Graph-Based Scene Representation2023 IEEE Intelligent Vehicles Symposium (IV)10.1109/IV55152.2023.10186641(1-8)Online publication date: 4-Jun-2023
https://doi.org/10.1109/IV55152.2023.10186641
Oberoi KDel Mondo GGaüzère BDupuis YVasseur P(2023)Detecting dynamic patterns in dynamic graphs using subgraph isomorphismPattern Analysis & Applications10.1007/s10044-023-01145-z26:3(1205-1221)Online publication date: 1-Aug-2023
https://dl.acm.org/doi/10.1007/s10044-023-01145-z
Peng YXie XLin MRan LYuan FZhou YTang L(2021)A Study of Sea Surface Rain Identification Based on HY-2A ScatterometerRemote Sensing10.3390/rs1317347513:17(3475)Online publication date: 1-Sep-2021
https://doi.org/10.3390/rs13173475
Show More Cited By

Index Terms

A Fast Backtracking Algorithm to Test Directed Graphs for Isomorphism Using Distance Matrices
1. Mathematics of computing
  1. Discrete mathematics
2. Theory of computation
  1. Design and analysis of algorithms
    1. Algorithm design techniques
      1. Backtracking

Recommendations

Directed domination in oriented graphs

A directed dominating set in a directed graph D is a set S of vertices of V such that every vertex u@?V(D)@?S has an adjacent vertex v in S with v directed to u. The directed domination number of D, denoted by @c(D), is the minimum cardinality of a ...
Fast edge searching and fast searching on graphs

Given a graph G=(V,E) in which a fugitive hides on vertices or along edges, graph searching problems are usually to find the minimum number of searchers required to capture the fugitive. In this paper, we consider the problem of finding the minimum ...
Biclique graphs and biclique matrices

A biclique of a graph G is a maximal induced complete bipartite subgraph of G. Given a graph G, the biclique matrix of G is a {0,1,-1} matrix having one row for each biclique and one column for each vertex of G, and such that a pair of 1, -1 entries in ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of the ACM

Journal of the ACM Volume 23, Issue 3

July 1976

175 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/321958

Issue’s Table of Contents

Copyright © 1976 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 1976

Published in JACM Volume 23, 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

100
Total Citations
View Citations
1,930
Total Downloads

Downloads (Last 12 months)125
Downloads (Last 6 weeks)17

Reflects downloads up to 09 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Tian YCarballo ALi RTakeda K(2023)RSG-Search: Semantic Traffic Scene Retrieval Using Graph-Based Scene Representation2023 IEEE Intelligent Vehicles Symposium (IV)10.1109/IV55152.2023.10186641(1-8)Online publication date: 4-Jun-2023
https://doi.org/10.1109/IV55152.2023.10186641
Oberoi KDel Mondo GGaüzère BDupuis YVasseur P(2023)Detecting dynamic patterns in dynamic graphs using subgraph isomorphismPattern Analysis & Applications10.1007/s10044-023-01145-z26:3(1205-1221)Online publication date: 1-Aug-2023
https://dl.acm.org/doi/10.1007/s10044-023-01145-z
Peng YXie XLin MRan LYuan FZhou YTang L(2021)A Study of Sea Surface Rain Identification Based on HY-2A ScatterometerRemote Sensing10.3390/rs1317347513:17(3475)Online publication date: 1-Sep-2021
https://doi.org/10.3390/rs13173475
Vasilchikov V(2021)Parallel Algorithm for Solving the Graph Isomorphism ProblemAutomatic Control and Computer Sciences10.3103/S014641162107016655:7(617-622)Online publication date: 1-Dec-2021
https://dl.acm.org/doi/10.3103/S0146411621070166
Wang RLiang DCao XGuo Y(2021)Semantic Correspondence with Geometric Structure AnalysisACM Transactions on Multimedia Computing, Communications, and Applications10.1145/344157617:3(1-21)Online publication date: 22-Jul-2021
https://dl.acm.org/doi/10.1145/3441576
Benreguia BMoumen H(2021)Some Consistency Rules for Graph MatchingSN Computer Science10.1007/s42979-021-01001-z3:2Online publication date: 29-Dec-2021
https://dl.acm.org/doi/10.1007/s42979-021-01001-z
Valiente GValiente G(2021)Graph IsomorphismAlgorithms on Trees and Graphs10.1007/978-3-030-81885-2_7(255-285)Online publication date: 12-Oct-2021
https://doi.org/10.1007/978-3-030-81885-2_7
Vasilchikov V(2020)Parallel Algorithm for Solving the Graph Isomorphism ProblemModeling and Analysis of Information Systems10.18255/1818-1015-2020-1-86-9427:1(86-94)Online publication date: 23-Mar-2020
https://doi.org/10.18255/1818-1015-2020-1-86-94
He JChen JHuang GGuo MZhang ZZheng HLi YWang RFan WChi CDing Wde Souza PChen BLi RShang JVan Zundert A(2020)A Fuzzy Theory Based Topological Distance Measurement for Undirected Multigraphs2020 IEEE International Conference on Fuzzy Systems (FUZZ-IEEE)10.1109/FUZZ48607.2020.9177559(1-10)Online publication date: Jul-2020
https://doi.org/10.1109/FUZZ48607.2020.9177559
Han ZZhang Z(2020)Multi-turn Dialogue System Based on Improved Seq2Seq Model2020 International Conference on Communications, Information System and Computer Engineering (CISCE)10.1109/CISCE50729.2020.00055(245-249)Online publication date: Jul-2020
https://doi.org/10.1109/CISCE50729.2020.00055
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

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

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents