Graph equivalence and characterization via a continuous evolution of a physical analog

2002/09/04 by Vladimir Gudkov, Gudkov, Vladimir, Shmuel Nussinov +1
Computer Science · Mathematics · Physics and Astronomy · #Combinatorics (math.CO) #Computational Physics (physics.comp-ph) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #FOS: Physical sciences #High Energy Physics - Phenomenology (hep-ph) #Statistical Mechanics (cond-mat.stat-mech) #cond-mat.stat-mech #cs.DM #hep-ph #math.CO #physics.comp-ph

paper · pdf · doi:10.48550/arxiv.cond-mat/0209112

RevTeX4

arxiv created 2002/09/06 · arxiv updated 2009/11/30

Abstract

A general novel approach mapping discrete, combinatorial, graph-theoretic problems onto ``physical'' models - namely n simplexes in n-1 dimensions - is applied to the graph equivalence problem. It is shown to solve this long standing problem in polynomial, short, time.

Related

• A class of quadratic difference equations on a finite graph
• Graph isomorphism: Physical resources, optimization models, and algebraic characterizations
• On the Solution of Graph Isomorphism by Dynamical Algorithms
• Graphings of arithmetical equivalence relations
• Testing Graph Isomorphism in Parallel by Playing a Game