Spectrally Robust Graph Isomorphism

DOI10.4230/LIPIcs.ICALP.2018.84zbMath1499.68280arXiv1805.00181OpenAlexW2962791331MaRDI QIDQ5002763

Alexandra Kolla, Ali Kemal Sinop, Ioannis Koutis, Vivek Madan

Publication date: 28 July 2021

Full work available at URL: https://arxiv.org/abs/1805.00181

zbMATH Keywords

graph isomorphismgraph similaritynetwork alignment

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items

The Complexity of Homomorphism Indistinguishability

Uses Software

• GHOST

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Isomorphism of graphs of bounded valence can be tested in polynomial time
• Fifty years of graph matching, network alignment and network comparison
• Practical graph isomorphism. II.
• On two geometric problems related to the travelling salesman problem
• Low Distortion Maps Between Point Sets
• Graph Embeddings and Laplacian Eigenvalues
• Toward Quantifying Vertex Similarity in Networks
• Graph isomorphism in quasipolynomial time [extended abstract]
• Hardness of Robust Graph Isomorphism, Lasserre Gaps, and Asymmetry of Random Graphs