๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Sensitivity analysis for shortest path problems and maximum capacity path problems in undirected graphs

โœ Scribed by Ramkumar Ramaswamy; James B. Orlin; Nilopal Chakravarti

Publisher
Springer-Verlag
Year
2004
Tongue
English
Weight
211 KB
Volume
102
Category
Article
ISSN
0025-5610

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

On the All-Pairs-Shortest-Path Problem i
On the All-Pairs-Shortest-Path Problem in Unweighted Undirected Graphs
โœ R. Seidel ๐Ÿ“‚ Article ๐Ÿ“… 1995 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 318 KB

We present an algorithm, APD, that solves the distance version of the all-pairs-shortest-path problem for undirected, unweighted \(n\)-vertex graphs in time \(O(M(n) \log n)\), where \(M(n)\) denotes the time necessary to multiply two \(n \times n\) matrices of small integers (which is currently kno

A simple linear algorithm for the edge-d
A simple linear algorithm for the edge-disjoint (s, t)-paths problem in undirected planar graphs
โœ Laurent Coupry ๐Ÿ“‚ Article ๐Ÿ“… 1997 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 400 KB

Let G = (v!E) be an undirected planar graph, and s, 1 E V, s # f. We present a linear algorithm to compute a set of edge-disjoint (s, t)-paths of maximum cardinality in G. In other words, the problem is to find a maximum unit flow from s to r in a non-weighted graph. The main purpose is not to show