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?
[ Parent
| on HN ]
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.