News for hackers. Stuff that matters.
Re:Quasi-Polynomial Algorithm for Graph Isomorphism by oofabz on Wednesday November 04, 2015 @02:54PM (#10509147)
Can anyone give an example of real-world problems that graph isomophism can be used to solve? I am out of my depth here and I might be able to make more sense of it if I had a concrete example to relate these concepts to.
Re:Quasi-Polynomial Algorithm for Graph Isomorphism by johncolanduoni on Wednesday November 04, 2015 @03:47PM (#10509583)
One application is electronic circuit verification. A conceptual circuit diagram needs to be mapped to a specific geometry of components and conductive paths between them. The verification that the circuit diagram matches the layout is a graph isomorphism problem; you need to ensure that you can assign the pre-layout components to the ones in the specific layout, such that all the edges line up with those in the original diagram.