bukzor wrote:

Can someone point me in the direction of a good solution of this? I'm

using it to construct a SQL query compiler, ....

Given a directed graph and a list of points in the graph, what is the

minimal subgraph that contains them all? It is preferable that the

subgraph is a tree.

I did something nice (but non-redistributable) on this once: here is the

driving intuition:

* Start with every point a distinct color.

* Add all points adjacent in the digraph as the same color; merge

colors as you join them.

* When you are down to to a single color, you have the minimal solution

in the set you've chosen.

I actually did a cheapest-first search; adding an edge each time.

There is a post-join pruning step that was (as I recall) fairly simple.

-Scott David Daniels

Sc***********@Acm.Org