Let us consider n directed acyclic graphs $(G_i)_{1\leq i \leq n}$ and G their cartesian product (with the induced edges) : G is still a DAG. Let us suppose that each vertex has a value, defined as the sum of the values of its children and that this value is known only for the leaves.

The problem is the efficient computation of the values for the vertices in $\prod_{1 \leq i \leq n} H_i$ for $H_i \subset G_i$ for every i.

My first idea would be, since G is a DAG:

1) to define the edges of the induced graph $(\prod_{1 \leq i \leq n} H_i) \cup L$ (L being the set of the leaves), thus giving the latter set a DAG structure

2) to apply topological ordering on this DAG and then recursively compute the missing values.

The first step is quite costly, as I have to find the induced edges for every node in H (complexity is at most quadratic in the number of induced edges).

The second step is not as costly, but still have a quadratic complexity (at most) due to the computation.

Most of all, this does not look very efficient, as this solution does not take advantage of the cartesian product!

How could I improve my current solution?

Thank you for any help you can offer.

  • Well, you can e.g. compute separately a “topological ordering” of each graph in the product, and then take their lexicographic product. – Emil Jeřábek Oct 9 at 19:31

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.