A question for anyone who has read Knuth
Feb. 16th, 2004 11:21 am(actually I have too, but the TeXbook isn't what I'm talking about). I thought maybe this was a problem that those of you who read computer science might have an idea about. I'm afraid the phyisicst's approach ("any combinatoric problem can be solved with enough nested DO loops") has led me to geometric overload.
Here's the problem... I even drew a diagram

Given a network like the one above (where only the topology matters), I need an algorithm to find the minimum set of links that joins the 3 nodes (marked with blobs).

To join the 3 nodes, one needs to use the 6 links marked in red, and include 4 additional nodes.
In general, I have a list of L links each of which connects two vertices. N of the V vertices need to be linked together, either directly or indirectly. (In my example, L=11, N=3, V=12.) How can I find which links and which additional nodes I need to do this? At the moment my problem has just one solution, but I may have to add additional connections which include a loop. It would be nice if the algorithm could pick the solution with fewest links. I guess this is related to the travelling salesman problem, though the problem is one of selection of cities to visit rather than order.
Don't worry, I'm not asking for the code to do this, just a hint about an algorithm. My current effort, trys including all combinations of links until it finds the smallest set that includes the desired nodes. That works fine, but requires L! iterations, and it's getting very slow :-(
What I'm actually trying to do is find out programatically which tables and joins are required for an SQL query that includes a subset of all the tables in the database.
Thanks!
PS. and if anyone has an analytic solution to the QCD Lagrangian, that too would be welcome :-)
Here's the problem... I even drew a diagram

Given a network like the one above (where only the topology matters), I need an algorithm to find the minimum set of links that joins the 3 nodes (marked with blobs).

To join the 3 nodes, one needs to use the 6 links marked in red, and include 4 additional nodes.
In general, I have a list of L links each of which connects two vertices. N of the V vertices need to be linked together, either directly or indirectly. (In my example, L=11, N=3, V=12.) How can I find which links and which additional nodes I need to do this? At the moment my problem has just one solution, but I may have to add additional connections which include a loop. It would be nice if the algorithm could pick the solution with fewest links. I guess this is related to the travelling salesman problem, though the problem is one of selection of cities to visit rather than order.
Don't worry, I'm not asking for the code to do this, just a hint about an algorithm. My current effort, trys including all combinations of links until it finds the smallest set that includes the desired nodes. That works fine, but requires L! iterations, and it's getting very slow :-(
What I'm actually trying to do is find out programatically which tables and joins are required for an SQL query that includes a subset of all the tables in the database.
Thanks!
PS. and if anyone has an analytic solution to the QCD Lagrangian, that too would be welcome :-)