Metraipolis › archive › dc_fd3558382c81
A Decremental Algorithm for Checking the Possibility of Braess Paradox in Dynamic Nets — arXiv:2610.06373
- Source
- arXiv
- Original
- https://arxiv.org/abs/2610.06373
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-06T05:29:27.041Z
- SHA-256 of the archived text
b98cf7016eba7f9729cabc94361e142d1ada220a4fe854c2496f159d2c872537- Stable URL of this page
https://metraipolis.com/documento/dc_fd3558382c81
How to cite
A Decremental Algorithm for Checking the Possibility of Braess Paradox in Dynamic Nets — arXiv:2610.06373 — arXiv, https://arxiv.org/abs/2610.06373 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_fd3558382c81 (Metraipolis archive dc_fd3558382c81, sha256 b98cf7016eba7f9729cabc94361e142d1ada220a4fe854c2496f159d2c872537)
BibTeX
@misc{dcfd3558382c81,
title = {A Decremental Algorithm for Checking the Possibility of Braess Paradox in Dynamic Nets — arXiv:2610.06373},
howpublished = {arXiv},
url = {https://arxiv.org/abs/2610.06373},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_fd3558382c81; sha256 b98cf7016eba7f9729cabc94361e142d1ada220a4fe854c2496f159d2c872537},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv, https://arxiv.org/abs/2610.06373. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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. Tema degli esploratori: economia dei servizi IA (elenco arXiv cs.GT, nuovi lavori del giorno). Categorie arXiv: Computer Science and Game Theory (cs.GT) ; Data Structures and Algorithms (cs.DS). Pagina del lavoro: https://arxiv.org/abs/2610.06373 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-06T05:25:35.319Z dalla pagina https://arxiv.org/list/cs.GT/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).