A Decremental Algorithm for Checking the Possibility of Braess Paradox in Dynamic Nets

概要

Braess paradox originates when latency at Wardrop equilibrium in traffic networks decreases because of removing edges. The graph-theoretic property of networks suffering from the Braess paradox was called vulnerability by Roughgarden in 2006; it was then characterized and algorithmically checked both for undirected and for directed nets. In this paper, we provide a decremental algorithm of linear amortized complexity to check vulnerability for dynamically evolving networks. The basic idea of our dynamic algorithm is to use a static algorithm that marks some edges as irrelevant for the vulnerability of the graph and ignore those edges for all subsequent runs of the decremental procedure. To get a linear amortized cost for every edge remotion, we also provide a new version of such a static algorithm that improves its complexity from O(n m^2) to O(m^2), that is in turn aligned with the cost of the best state-of-the-art static algorithm for vulnerability.

参考リンク

• Paper ↗

リンク先のライセンス・再現性・データ条件をご確認ください。自動分類や実装の目安は保証ではありません。

実装を始めるプロンプト

参考リンクを確認したうえで、次の内容をコピーして利用できます。

# 論文・記事
A Decremental Algorithm for Checking the Possibility of Braess Paradox in Dynamic Nets

# 概要
Braess paradox originates when latency at Wardrop equilibrium in traffic networks decreases because of removing edges. The graph-theoretic property of networks suffering from the Braess paradox was…

# 原典
https://arxiv.org/abs/2610.06373

上記の手法を実装してください。実行前に依存関係とライセンスを確認してください。