Reconstructing edge-disjoint paths |
| |
Authors: | M. Conforti R. Ravi |
| |
Affiliation: | a Dipartimento di Matematica Pura ed Applicata, Universitá di Padova, Via Belzoni 7, 35131 Padova, Italy b Department of Statistics and Operations Research, School of Mathematical Sciences, Tel-Aviv University, Tel Aviv 69978, Israel c GSIA, Carnegie Mellon University, Pittsburgh, PA 15213, USA |
| |
Abstract: | For an undirected graph G=(V,E), the edge connectivity values between every pair of nodes of G can be succinctly recorded in a flow-equivalent tree that contains the edge connectivity value for a linear number of pairs of nodes. We generalize this result to show how we can efficiently recover a maximum set of disjoint paths between any pair of nodes of G by storing such sets for a linear number of pairs of nodes. At the heart of our result is an observation that combining two flow solutions of the same value, one between nodes s and r and the second between nodes r and t, into a feasible flow solution of value f between nodes s and t, is equivalent to solving a stable matching problem on a bipartite multigraph.Our observation, combined with an observation of Chazelle, leads to a data structure, which takes O(n3.5) time to generate, that can construct the maximum number λ(u,v) of edge-disjoint paths between any pair (u,v) of nodes in time O(α(n,n)λ(u,v)n) time. |
| |
Keywords: | flow equivalent tree stable matching |
本文献已被 ScienceDirect 等数据库收录! |
|