Graph matching in theory and practice
Author: 
Neil SavageAuthors Info & Claims
Abstract
A theoretical breakthrough in graph isomorphism excites complexity experts, but will it lead to any practical improvements?
References
[1]
Babai, L. Graph Isomorphism in Quasipolynomial Time, arXiv, Cornell University Library, 2015, http://arxiv.org/abs/1512.03547.
[2]
McKay, B.D., and Piperno, A. Practical Graph Isomorphism II, Journal of Symbolic Computation, 60, 2014, http://arxiv.org/abs/1301.1493.
[3]
Fortnow, L. The status of the P versus NP problem, Communications of the ACM, September 2009, http://cacm.acm.org/magazines/2009/9/38904-the-status-of-the-p-versus-np-problem/fulltext.
[4]
Fortnow, L., and Grochow, J.A. Complexity classes of equivalence problems revisited, Information and Computation, 209, 2011, http://arxiv.org/pdf/0907.4775.pdf.
[5]
Isomorphic Graphs, Example 1, Stats-Lab Dublin https://www.youtube.com/watch?v=Xq8o-z1DsUA.
Index Terms
- Graph matching in theory and practice
Recommendations
On two problems in graph Ramsey theory
We study two classical problems in graph Ramsey theory, that of determining the Ramsey number of bounded-degree graphs and that of estimating the induced Ramsey number for a graph with a given number of vertices.
The Ramsey number r ( H ) of a graph ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
July 2016
118 pages
Copyright © 2016 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 24 June 2016
Published in CACM Volume 59, Issue 7
Check for updates
Qualifiers
- Research-article
- Popular
- Pre-selected
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 6,564Total Downloads
- Downloads (Last 12 months)149
- Downloads (Last 6 weeks)24
Reflects downloads up to 04 Feb 2025
Other Metrics
Citations
View Options
View options
View or Download as a PDF file.
PDFeReader
View online with eReader.
eReaderDigital Edition
View this article in digital edition.
Digital EditionMagazine Site
View this article on the magazine site (external)
Magazine SiteLogin options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in