Live briefing
Everything about Graph isomorphism problem
Unsolved problem in computational complexity theory
The graph isomorphism problem is the computational problem of determining whether two finite graphs are isomorphic. Wikipedia →
🧭 Start here: a 6-step reading path
- Read the overview: Graph isomorphism problemA 5-minute orientation
- Skim a recent paper: A Quantum Algorithm for the Sub-graph Isomorphism ProblemInfluential work since 2022
- Pick up a classic book: Discrete Mathematics and Its ApplicationsThe most-reprinted book on the subject
- Read the landmark paper: A note on the graph isomorphism counting problemCited 127 times
- Go sideways: László BabaiA closely related topic
- Go sideways: Graph canonizationA closely related topic
📖 Definitions
No dictionary entry for this exact phrase.
🗂️ The subject at a glance
🏆 Landmark papers (most cited)
A note on the graph isomorphism counting problem
Two-particle quantum walks applied to the graph isomorphism problem
A classical approach to the graph isomorphism problem using quantum walks
The graph isomorphism problem
Graph isomorphism problem
Generalized Matrix Functions and the Graph Isomorphism Problem
QUBO formulations for the graph isomorphism problem and related problems
Experimental quantum annealing: case study involving the graph isomorphism problem
🆕 Influential since 2022
A Quantum Algorithm for the Sub-graph Isomorphism Problem
The isomorphism problem for graph magma algebras
Portable network resolving huge-graph isomorphism problem
Definable Ellipsoid Method, Sums-of-Squares Proofs, and the Graph Isomorphism Problem
Rethinking Graph Classification Problem in Presence of Isomorphism
📚 Books worth reading
Discrete Mathematics and Its ApplicationsKenneth H. Rosen · 1988
Mathematical structures for computer scienceJudith L. Gersting · 1982
Zeta functions of graphsAudrey Terras · 2010
Discrete mathematicsNorman Biggs · 1985
Algorithms in computational molecular biologyMourad Elloumi · 2010
Graph theory with applications to engineering and computer scienceNarsingh Deo, Narsingh Deo · 1974
The graph isomorphism problemJohannes Köbler, J. Kobler · 1993
Discrete mathematics with graph theoryEdgar G. Goodaire · 1998
Ranked by number of editions on Open Library, a rough measure of how lasting a book is.
🔗 Related topics
- László Babai László "Laci" Babai (born July 20, 1950, in Budapest) is a Hungarian-American professor of computer science and mathematics at the University of Chicago…
- Graph canonization In graph theory, a branch of mathematics, graph canonization is the problem of finding a canonical form of a given graph G. A canonical form is a labeled…
- Graph isomorphism In graph theory, an isomorphism of graphs G and H is a bijection between the vertex sets of G and H f:V(G)→V(H) such that any two vertices u and v of G…
- Eugene M. Luks Eugene Michael Luks (born circa 1940) is an American mathematician and computer scientist, a professor emeritus of computer and information science at…
- NP-intermediate In computational complexity, problems that are in the complexity class NP but are neither in the class P nor NP-complete are called NP-intermediate, and…
- NP-completeness In computational complexity theory, NP-complete problems are the hardest of the problems to which solutions can be verified quickly. NP is short for "nondetermi…
- Subgraph isomorphism problem In theoretical computer science, the subgraph isomorphism problem is a computational task in which two graphs G {\displaystyle G} and H {\displaystyle…
- List of NP-complete problems This is a list of some of the more commonly known problems that are NP-complete when expressed as decision problems. As there are thousands of such problems…