Network characterizations for excluding Braess's paradox

DOI10.1007/S00224-016-9710-4MaRDI QIDQ506543zbMATH OpenOpenAlexFDO

Authors Zhuo Diao, Xujin Chen, Xiaodong Hu

Publication date 1 February 2017

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00224-016-9710-4

zbMATH Keywords

series-parallel graphBraess's paradoxmulti-commodity networknonatomic selfish routingsingle-commodity network

Mathematics Subject Classification ID

Traffic problems in operations research (90B20) Games involving graphs (91A43)

Recommendations

• Excluding Braess's paradox in nonatomic selfish routing
• Braess's Paradox in large random graphs
• Matroids are immune to Braess' paradox
• On the severity of Braess's paradox: designing networks for selfish users is hard
• Stronger bounds on Braess's paradox and the maximum latency of selfish routing

Cites work

• scientific article; zbMATH DE number 1432797 (Why is no real title available?)
• Approximation and Online Algorithms
• Efficient graph topologies in network routing games
• Finding k Disjoint Paths in a Directed Planar Graph
• How bad is selfish routing?
• Inefficiencies in network models: a graph-theoretic perspective
• Matroids are immune to Braess' paradox
• Network structure and strong equilibrium in route selection games.
• Network topology and the efficiency of equilibrium
• On the hardness of network design for bottleneck routing games
• On the severity of Braess's paradox: designing networks for selfish users is hard
• Strong equilibrium in network congestion games: increasing versus decreasing costs
• Stronger bounds on Braess's paradox and the maximum latency of selfish routing
• The Recognition of Series Parallel Digraphs
• The directed subgraph homeomorphism problem
• Topological Conditions for Uniqueness of Equilibrium in Networks
• Worst-case equilibria
• Über ein Paradoxon aus der Verkehrsplanung

Cited in

(16)

• Inefficiencies in network models: a graph-theoretic perspective
• A polynomial-time algorithm for detecting the possibility of Braess paradox in directed graphs
• Matroids are immune to Braess' paradox
• Excluding Braess's paradox in nonatomic selfish routing
• Efficient black-box reductions for separable cost sharing
• Efficient black-box reductions for separable cost sharing
• A Characterization of Undirected Graphs Admitting Optimal Cost Shares
• A faster algorithm for recognizing directed graphs invulnerable to Braess's paradox
• Unreasonable implications of reasonable idiotypic network assumptions
• Informational Braess' paradox: the effect of information on traffic congestion
• A note on social learning in non-atomic routing games
• Social learning in nonatomic routing games
• On weak Pareto optimality of nonatomic routing networks
• Depletable channels: dynamics, behaviour, and efficiency in network design
• Escaping Braess's paradox through approximate Caratheodory's theorem
• Polynomial recognition of vulnerable multi-commodities

This page was built for publication: Network characterizations for excluding Braess's paradox

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q506543)