An embedded and charset-unspecified text was scrubbed... Name: not available URL: <https://stat.ethz.ch/pipermail/r-help/attachments/20120801/4a46cc80/attachment.pl>
Efficient deterministic algorithm for Matching Weighted Graphs with bounded degree.
2 messages · khris, Petr Savicky
On Wed, Aug 01, 2012 at 06:19:29AM -0700, khris wrote:
Hi Petr, The following is different line of thought which is posted in different form, maybe you have some wise input on it. "I need to find Efficient(tracktable) deterministic algorithm for Matching Weighted Graphs with bounded degree. Now we all know Graph matching is non-tractable but when degree of vertex has upper bound are there any tractable algorithm? Does this special case comes under 'Finite Parameter Tractability' ? Also we know that Graph isomorphism where degree of vertex has upper bound has tractable algorithms. So will it be possible to reduce the Graph matching problem with bounded degree to Graph isomorphism of bounded degree problem then our original problem will have tractable solution. Appreciate any help or pointer which may take us close towards the solutions."
Hi. There is currently another thread concerning search of graph isomorphism using package "igraph". May be, you can learn something from there. https://stat.ethz.ch/pipermail/r-help/2012-July/320141.html https://stat.ethz.ch/pipermail/r-help/2012-August/320225.html Petr.