Graph matching using the interference of continuous-time quantum walks

J. Köbler, On graph isomorphism for restricted graph classes, in: CiE, 2006, pp. 241–256.

L. Babai, D.Yu. Grigoryev, D.M. Mount, Isomorphism of graphs with bounded eigenvalue multiplicity, in: STOC ’82: Proceedings of the Fourteenth Annual ACM Symposium on Theory of Computing, ACM Press, New York, NY, USA, 1982, pp. 310–324.

J.E. Hopcroft, J.K. Wong, A linear time algorithm for isomorphism of planar graphs, in: Proceedings of the 6th Annual ACM Symposium on the Theory of Computing (STOC’74), 1974, pp. 172–184.

McKay, 1981, Practical graph isomorphism, Congr. Numer., 30, 45

Ullmann, 1976, An algorithm for subgraph isomorphism, J. ACM, 23, 31, 10.1145/321921.321925

Luo, 2001, Structural graph matching using the EM algorithm and singular value decomposition, Pattern Anal. Mach. Intell., 23, 1120, 10.1109/34.954602

A. Robles-Kelly, E. Hancock, Graph matching using spectral seriation and string edit distance, in: GbRPR 2003, 2003.

Messmer, 1999, A decision tree approach to graph and subgraph isomorphism detection, Pattern Recognition, 32, 1979, 10.1016/S0031-3203(98)90142-X

Sanfeliu, 1983, A distance measure between attributed relational graphs for pattern recognition, IEEE Trans. Systems, Man Cybern., 13, 353, 10.1109/TSMC.1983.6313167

Christmas, 1995, Structural matching in computer vision using probabilistic relaxation, IEEE Trans. Pattern Anal. Mach. Intell., 17, 749, 10.1109/34.400565

Shapiro, 1982, Organization of relational models for scene analysis, IEEE Trans. Pattern Anal. Mach. Intell., 4, 595, 10.1109/TPAMI.1982.4767312

Eshera, 1984, A graph distance measure for image analysis, IEEE Trans. Systems, Man Cybern., 14, 398, 10.1109/TSMC.1984.6313232

Horaud, 1989, Stereo correspondence through feature grouping and maximal cliques, IEEE Trans. Pattern Anal. Mach. Intell., 11, 1168, 10.1109/34.42855

Bunke, 1997, On a relation between graph edit distance and maximum common subgraph, Pattern Recognition Lett., 18, 689, 10.1016/S0167-8655(97)00060-3

Robles-Kelly, 2005, Graph edit distance from spectral seriation, IEEE Trans. Pattern Anal. Mach. Intell., 27, 365, 10.1109/TPAMI.2005.56

L. Grover, A fast quantum mechanical algorithm for database search, in: Proceedings of the 28th Annual ACM Symposium on the Theory of Computation, New York, NY, ACM Press, New York, 1996, pp. 212–219.

Jozsa, 2001, Quantum factoring, discrete logarithms, and the hidden subgroup problem, Comput. Sci. Eng., 3, 34, 10.1109/5992.909000

R. Beals. Quantum computation of Fourier transforms over symmetric groups, in: Proceedings of the 29th Annual ACM Symposium on the Theory of Computation (STOC), Texas, ACM Press, New York, 1997, pp. 48–53.

J. Kempe, A. Shalev, The hidden subgroup problem and permutation group theory, in: Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, Vancouver, British Columbia, 2005, pp. 1118–1125, ISBN:0-89871-585-7.

M. Ettinger, P. Høyer, A quantum observable for the graph isomorphism problem, 1999, arXiv:quant-ph/9901029.

Kempe, 2003, Quantum random walks—an introductory overview, Contemp. Phys., 44, 307, 10.1080/00107151031000110776

Farhi, 1998, Quantum computation and decision trees, Phys. Rev. A, 58, 915, 10.1103/PhysRevA.58.915

D. Aharonov, A. Ambainis, J. Kempe, U. Vazirani, Quantum walks on graphs, in: STOC ’01: Proceedings of the ACM Theory of Computing, ACM Press, New York, 2001, pp. 50–59.

A. Ambainis, E. Bach, A. Nayak, A. Vishwanath, J. Watrous, One-dimensional quantum walks, in: Proceedings of the 33th STOC, New York, NY, ACM, New York, 2001, pp. 60–69.

J. Kempe, Quantum random walks hit exponentially faster, in: Proceedings of the 7th International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM’03), 2003, pp. 354–369.

Childs, 2002, An example of the difference between quantum and classical random walks, Quantum Inf. Process., 1, 35, 10.1023/A:1019609420309

A.M. Childs, R. Cleve, E. Deotto, E. Farhi, S. Gutmann, D.A. Spielman, Exponential algorithmic speedup by a quantum walk, in: STOC ’03: Proceedings of the 35th ACM Symposium on TOC, New York, NY, USA, ACM Press, New York, 2003, pp. 59–68.

V. Gudkov, S. Nussinov, Graph equivalence and characterization via a continuous evolution of a physical analog, 2002 (cond-mat/0209112).

Shiau, 2005, Physically-motivated dynamical algorithms for the graph isomorphism problem, Quantum Inf. Comput., 5, 492

Sarti, 2005, Exact and approximate graph matching using random walks, IEEE Trans. Pattern Anal. Mach. Intell., 27, 1100, 10.1109/TPAMI.2005.138

Kuhn, 1955, The Hungarian method for the assignment problem, Naval Res. Logistic Q., 2, 83, 10.1002/nav.3800020109

Barrow, 1976, Subgraph isomorphism, matching relational structures and maximal cliques, Inf. Process. Lett., 4, 83, 10.1016/0020-0190(76)90049-1

Barrow, 1976, Subgraph isomorphism, matching relational structures and maximal cliques, Inf. Process. Lett., 4, 83, 10.1016/0020-0190(76)90049-1

Pelillo, 1995, Relaxation labelling networks for the maximum clique problem, J. Artif. Neural Networks, 2, 313

Umeyama, 1988, An eigen decomposition approach to weighted graph matching problems, Pattern Anal. Mach. Intell., 10, 695, 10.1109/34.6778

Zhang, 2008, Graph spectral image smoothing using the heat kernel, Pattern Recognition, 41, 3328, 10.1016/j.patcog.2008.05.007

Gold, 1996, A graduated assignment algorithm for graph matching, IEEE Trans. Pattern Anal. Mach. Intell., 18, 377, 10.1109/34.491619

Wilson, 1997, Structural matching by discrete relaxation, IEEE Trans. Pattern Anal. Mach. Intell., 19, 634, 10.1109/34.601251

Scott, 1991, An algorithm for associating the features of two patterns, Proc. R. Soc. London B, 244, 10.1098/rspb.1991.0045

Douglas, 2008, A classical approach to the graph isomorphism problem, J. Phys. A Math. Theor., 41, 1, 10.1088/1751-8113/41/7/075303