A faster algorithm for recognizing directed graphs invulnerable to Braess's paradox
The authors in this paper consider the problem of deciding if, for a given graph with prescribed source and sink vertices, Braess's paradox does not occur for any cost functions. They propose a faster \(O(m^2)\) time algorithm to solve this problem for directed graphs. Their approach is based on a simple implementation of a known characterization that the subgraph of a given graph induced by all source-sink paths is series-parallel. The algorithm given by them here can be used to design a faster \(O(km^2)\) time algorithm for directed graphs with \(k\) source-sink pairs, which improves the previous \(O(knm^2)\) time algorithm already available in the literature. The faster running time is achieved by speeding up the simple implementation using another characterization that a certain structure is embedded in the given graph.\N\NFor the entire collection see [Zbl 1520.90003].
This page was built for publication: A faster algorithm for recognizing directed graphs invulnerable to Braess's paradox
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6591943)
