辺の重みが Monge 性を満たすような完全 DAG について、辺を丁度 $d$ 本使う条件下での $0$-$(N - 1)$ 最短路長を $\Theta (N \log(\max _ {e \in E} \lvert c(e) \rvert))$ で計算する。 ラグランジュ双対問題との強双対性が $c$ の Monge 性から成り立ち、ラグランジュ緩和問題もまた Monge 性を利用して高速に解くこと…