Our paper on “Efficient Algorithms for Listing K Disjoint st-Paths in Graphs” has been accepted for LATIN 2018, which will be held in Buenos Aires. Thanks to my coauthors Roberto Grossi and Luca Versari.
Given a connected graph G of m edges and n vertices, we consider the basic problem of listing all the choices of k vertex-disjoint st-paths, for any two input vertices s,t of G and a positive integer k. Our algorithms take O(m) time per solution, using O(m) space and requiring O(F_k(G)) setup time, where F_k(G) = O(m min{k, n^{2/3} log n, sqrt{m} log n} ) is the cost of running a max-flow algorithm on~G to compute a flow of size k. The proposed techniques are simple and apply to other related listing problems as discussed in the paper.