7
$\begingroup$

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?

  1. Are there other papers that use embedded dynamic programming?
  2. 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.

  1. 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.

Improve this question
$\endgroup$
2
  • 3
    $\begingroup$ In many dynamic programs, in order to compute the cell M[i,j], you look at the cells M[i-1,j], M[i,j-1] and M[i-1,j-1]. In what way is this NOT embedded dynamic programming, since you're only considering "a relevant subset of the precomputed instances" ? $\endgroup$
    – Suresh Venkat
    Feb 11, 2011 at 20:49
  • $\begingroup$ @Suresh: Well, yes. It might be a distinction without a difference, which is part of my question motivation, to be honest. I will try to get a better grasp of his algorithm and post a question edit in a few days. $\endgroup$
    – Aaron Sterling
    Feb 12, 2011 at 1:17

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.