DAG内の重複しない重複経路の最大重み

重み付けされたDAG $ G $があるとします。 $ m $ -path-tupleは、$ P_i $がグラフ上のパスであり、$
P_i $と$ P_j
$がエッジを共有しない$(P_1、…、P_m)$として定義されます。言い換えれば、グラフの各エッジは、これらのパスのせいぜい1つに属する。これらの$
m $ -path-tuplesの中で、最大の重みを持つもの、つまりそのエッジの重みの合計が他の$ m $
-path-tupleよりも大きいものを探したいとします。

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.

ベストアンサー
申し訳ありませんが、適切な答えはありません

返信を残す

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