arXiv preprint ·
An Incremental Algorithm for Checking the Possibility of Braess Paradox in Dynamic Nets
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
Braess paradox is a well-known phenomenon that originates when latency at Wardrop equilibrium in traffic networks decreases because of removing edges. The possibility of having the paradox was called vulnerability by Roughgarden in 2006 and was characterized later on by graph-theoretical notions, both for undirected and for directed graphs. In this paper we provide an algorithm for the incremental case of checking vulnerability for dynamically evolving graphs. The crucial idea to keep the amortized cost linear for every edge addition is that we do not need to run the vulnerability algorithm on the whole graph, but only on a well-identified subgraph, determined by the edge that we are adding. Overall, to add m edges, we pay a cost of O(m2); this aligns with the O(m2) cost of the state-of-the-art static algorithm for vulnerability.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Computer Science & Game Theory
Beyond Provenance: The Economics and Governance of Personalized AI Memory
The Facility Advantage in the One-Round Discrete Voronoi Game on a Line
Behavior is Not Enough: A Mechanism-Based Evaluation of Social Norm Emergence in LLM Societies
Optimal High-Order Methods for Solving Monotone Variational Inequalities
Building Socio-Affective Artificial Intelligence for Interactive Multi-Agent Simulations
Get the few papers worth your time in Computer Science & Game Theory every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.