Faster algorithms for shortest path and network flow based on graph decomposition

Manas Jyoti Kashyop ; Tsunehiko Nagayama ; Kunihiko Sadakane

Journal of Graph Algorithms and Applications, Special Issue on Selected Papers from the 12th International Conference and Workshops on Algorithms and Computation, WALCOM 2018 , Tome 23 (2019) no. 5, pp. 781-813.

Résumé

We propose faster algorithms for the maximum flow problem and shortest path problems based on graph decomposition. Our algorithms first construct indices (data structures) from a given graph, then use them for solving the problems. Time complexities of our algorithms depend on the size of the maximum triconnected component in the graph, say $r$. Max flow indexing problem is a basic network flow problem, which consists of two phases. In a preprocessing phase we construct an index and in a query phase we process the query using the index. We can solve all pairs maximum flow problem and minimum cut problem using the indices. Our algorithms run faster than known algorithms if $r$ is small. The maximum flow problem can be solved in $\mathcal{O}(nr)$ time, which is faster than the best known $\mathcal{O}(nm)$ algorithm [Orlin, STOC 2013] if $r = o(m)$, where $n$ and $m$ are the numbers of vertices and edges in the given network, respectively. Distance oracle problem is a basic problem in shortest path, consisting of two phases. In preprocessing phase we construct index and in query phase we use the index to find shortest path between two vertices. We use these indices to solve single source shortest path and all pair shortest path problems. If the given graph is undirected and all the weights are non-negative integers, then our algorithm finds shortest path between two vertices in $\mathcal{O}(m)$ time. If the given graph is directed or the weights are non-negative real numbers then our algorithm finds shortest path between two vertices in $\mathcal{O}(m + n \log r)$ time. If the edge weights are real numbers (i.e some of the weights are negative) then our algorithm finds shortest path between two vertices in $\mathcal{O}(m + nr)$ time.

Détail

DOI : 10.7155/jgaa.00512