Home  Issues  About JGAA  Instructions for Authors 
Special Issue on Selected Papers from the 12th International Conference and Workshops on Algorithms and Computation, WALCOM 2018
DOI: 10.7155/jgaa.00512
Faster algorithms for shortest path and network flow based on graph decomposition
Vol. 23, no. 5, pp. 781813, 2019. Regular paper.
Abstract 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 nonnegative 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 nonnegative 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.

Submitted: March 2018.
Reviewed: February 2019.
Revised: March 2019.
Accepted: April 2019.
Final: September 2019.
Published: October 2019.

Journal Supporters
