重み付けされたDAG $ G $があるとします。 $ m $ -path-tupleは、$ P_i $がグラフ上のパスであり、$
P_i $と$ P_j
m $ -path-tuplesの中で、最大の重みを持つもの、つまりそのエッジの重みの合計が他の$ m $

A max-flow min-cost formulation: We connect
every vertex without incoming edge to source and every vertex
without outgoing edge to sink. Also we set the capacity of every
edge edge to 1, and then setting the capacity of the source to $m$.
In the end we set the cost of each edge to $-w(e)$ and minimise the
cost via a “max-flow-min-cost” method. The $capacity=1$ makes sure
the paths won’t have any edge in common, while minimising the cost
would effectively maximise the total weight. The problem with this
approach is that it introduces negative weights and therefore
solving it is quite slow. I was wondering if is a better way to
solve it given that it’s a DAG and not any arbitrary graph.



メールアドレスが公開されることはありません。 * が付いている欄は必須項目です