News for hackers. Stuff that matters.
Re:Quasi-Polynomial Algorithm for Graph Isomorphism by espes on Wednesday November 04, 2015 @02:48PM (#10509103)
Why is general graph isomorphism needed for that?
Re:Quasi-Polynomial Algorithm for Graph Isomorphism by ThePhysicist on Thursday November 05, 2015 @05:07AM (#10512561)
Probably it isn't, but if there was a general-purpose algorithm that I could just use without doing any hand-crafted optimizations that would be a huge win. As you said, finding a good solution is usually possible but it requires applying a lot of (reasonable) approximations and shortcuts.
Re:Quasi-Polynomial Algorithm for Graph Isomorphism by espes on Thursday November 05, 2015 @08:23AM (#10513123)
But it sounds like your model isn't a general graph? DAG and tree isomorphism is in P (and pretty straightforward), and so is tree edit distance...
Re:Quasi-Polynomial Algorithm for Graph Isomorphism by ThePhysicist on Thursday November 05, 2015 @11:02AM (#10514055)
ASTs are DAGs indeed, but as soon as you add semantic information to the mix the graph usually becomes cyclic.