Bounds on maximum concurrent flow in random bipartite graphs
- PDF / 650,893 Bytes
- 13 Pages / 439.37 x 666.142 pts Page_size
- 9 Downloads / 239 Views
Bounds on maximum concurrent flow in random bipartite graphs Fernando E. Vilas1
· Eli V. Olinick1 · David W. Matula1
Received: 6 September 2019 / Accepted: 31 January 2020 © Springer-Verlag GmbH Germany, part of Springer Nature 2020
Abstract Algorithms that exploit the duality between maximum concurrent flow and sparse cuts in a graph can effectively discover hierarchical community structures in social networks. We analyze the maximum concurrent flow on random bipartite graphs and compare the results to two bounds based on graph structure.. The minimum degree bound is based on a sparse cut that removes a node of minimum degree. The other is the “gridlock” bound, where all edges are saturated with flow. We show that the gridlock bound is more constraining when the minimum degree of the graph is sufficiently large, and provide a way to calculate this bound on graphs of diameter three, which occurs with high probability on larger random bipartite graphs. Keywords Random graphs · Bipartite graphs · Maximum concurrent flow problem
1 Introduction The maximum concurrent flow problem (MCFP) is a computationally challenging network flow problem with applications in transportation, telecommunications, VLSI circuit design, and data clustering for biological taxonomy and social network analysis (SNA). Some authors have approached the problem as one of max-min fair flow, especially when viewing maximum concurrent flow as a “water filling” algorithm [15,22]. An instance of the MCFP is defined on an undirected graph G = (V , E) where each edge e ∈ E has capacity for ci j units of flow and there is demand for di j units
B
Fernando E. Vilas [email protected] Eli V. Olinick [email protected] David W. Matula [email protected]
1
Southern Methodist University, Dallas, TX, USA
123
F. E. Vilas et al.
of flow between each distinct pair of nodes i and j in V . We denote the set of all distinct pairs of nodes by D, and the set of all paths between end nodes i and j for demand pair {i, j} ∈ D by Pi j . The union of Pi j over all demand pairs is denoted by P, and the set of edges in path p ∈ P is denoted by E p . Using this notation, the edge-path model of the MCFP is to maximize the throughput z subject to (1) f = zd ∀{i, j} ∈ D, and (2) p i j p∈Pi j { p∈P:{i, j}∈E p } f p ≤ ci j ∀{i, j} ∈ E, where f p ≥ 0 is the amount of flow on path p ∈ P. The first constraint ensures a common throughput for all demand pairs, and the second enforces the capacity limits on the edges. We further denote an optimal flow function that solves the LP as f ∗ giving the resulting optimal flow along a specific path p as f ∗ ( p). Although it is computationally polynomial, the MCFP is a challenging problem because, “[it] gives rise to extremely difficult linear programs instances of a size and type relevant to applications often prove beyond the reach of state-of-the-art linear programming codes” [5]. Furthermore, there is no known combinatorial algorithm for the MCFP except for the special case of a single supply node [4]. In prior art
Data Loading...
