1
$\begingroup$

When a given weighted directed acyclic graph represents some object flow, what is the most efficient algorithm to find the equivalent graph sum of which edges is minimum? Here, 'equivalent' means the end state of the objects is the same.

The picture below is the trivial example of this problem.

enter image description here

Above, 'simplest' means least weight sum.

updated

Sorry, my problem specification was ambiguous. I updated the sample problem explanation.

update 2

To clarify the specification, I provide mathematical formulation.

Definition 1 transport mass map

Transport mass map T is a map between directed weighted graph to a set of pairs of node and transported volume.

for example, enter image description here

Definition 2 equivalence in terms of transportation

In this problem, two graphs G1 and G2 are equivalent iff T(G1) is T(G2) the same sets.

enter image description here

Lemma 1 equivalence relation

If G1 ~ G2 means G1 is equivalent with G2 in this sense, ~ is equivalence relation in a directed weighted graph set.

Definition 3 equivalence set

For graph G, S*(G) is a set of graph such that if a graph g in S*(G), g~G, and vice versa.

Definition 3 minimal graph in terms of transportation

Graph G- is called minimal for G iff the sum of G-'s node weights is minimum of all graph in S*(G)

Problem statement 1

What is (the most) efficient method to find G- when G is given.

Problem statement 2 (added)

What is the method above called generally?

Improve this question
$\endgroup$
4
  • 6
    $\begingroup$ The specification of your problem is not clear to me. Why is the second graph the answer to the first graph in your example? $\endgroup$
    – hengxin
    Jan 28, 2015 at 9:31
  • $\begingroup$ @hengxin Sorry, I updated the sample problem explanation. $\endgroup$
    – Light Yagmi
    Jan 31, 2015 at 23:49
  • 1
    $\begingroup$ I can't understand what you mean by "equivalent graph sum of which edges is minimum"? Please give a more careful definition of all terms, and elaborate on the problem description. Perhaps you might want to use mathematics. For instance, I don't know what you mean by "equivalent graph sum" or even "graph sum". I don't know what "object flow" means. I don't know what you're trying to minimize. $\endgroup$
    – D.W. ♦
    Feb 1, 2015 at 18:55
  • $\begingroup$ Rather than adding "updates", please edit your question so that people can just start reading at the top and find everything they need to know, in the logical order. "Update" is only useful to people who read the question before and remember exactly what it said. Questions stay forever so most people who will read it haven't yet seen it: you should optimize for them, not for the 29 people who've already looked at it. $\endgroup$
    – David Richerby
    Feb 8, 2015 at 15:39

0

Reset to default

Browse other questions tagged or ask your own question.