In Planar Subgraph Isomorphism Revisited, Frederic Dorn obtains an improved algorithm for Planar Subgraph Isomorphism, by using a technique he calls Embedded Dynamic Programming. This technique appears to me to be a generalization of dynamic programming, in that it builds up from the smallest possible instances, but then, to obtain the next stage, one considers only a relevant subset of the already-computed subinstances, instead of considering all of them.
I am interested both in the planar subgraph isomorphism problem, and in the embedded dynamic programnming technique.
A search on the phrase "embedded dynamic programming" is unhelpful, and it seems to me that this idea is close enough to dynamic programming that (some variant of) it might have been used in the past, for another problem, under another name. Does anybody know anything about this?
- Are there other papers that use embedded dynamic programming?
- Are there pre-existing techniques in the literature that are "cousins" to this approach?
I am also interested in implementability. My not-very-serious-yet review of Dorn's paper makes me think his algorithm might be usefully implementable. Motivation here: most (empirical definition of most) molecular graphs are planar. The subgraph isomorphism implementations for molecular graphs have been optimized over a period of years, so they would be hard to beat in practice. Still, if this is a fundamentally new approach without a lot of hidden constants, then there might be something really exciting here.
- Do you think Dorn's algorithm is realistically implementable? Or could a simple variation have that property?
Thanks, and I hope this question is more sensible than my last one, which was a bit of a disaster.