On Polynomial-Time Combinatorial Algorithms for Maximum L-Bounded Flow
K Altmanová, P Kolman, J Voborník - Workshop on Algorithms and Data …, 2019 - Springer
K Altmanová, P Kolman, J Voborník
Workshop on Algorithms and Data Structures, 2019•SpringerGiven a graph G=(V, E) with two distinguished vertices s, t∈ V and an integer L, an L-
bounded flow is a flow between s and t that can be decomposed into paths of length at most
L. In the maximum L-bounded flow problem the task is to find a maximum L-bounded flow
between a given pair of vertices in the input graph. The problem can be solved in polynomial
time using linear programming. However, as far as we know, no polynomial-time
combinatorial algorithm for the L-bounded flow is known. The only attempt, that we are …
bounded flow is a flow between s and t that can be decomposed into paths of length at most
L. In the maximum L-bounded flow problem the task is to find a maximum L-bounded flow
between a given pair of vertices in the input graph. The problem can be solved in polynomial
time using linear programming. However, as far as we know, no polynomial-time
combinatorial algorithm for the L-bounded flow is known. The only attempt, that we are …
Abstract
Given a graph with two distinguished vertices and an integer L, an L-bounded flow is a flow between s and t that can be decomposed into paths of length at most L. In the maximum L-bounded flow problem the task is to find a maximum L-bounded flow between a given pair of vertices in the input graph.
The problem can be solved in polynomial time using linear programming. However, as far as we know, no polynomial-time combinatorial algorithm for the L-bounded flow is known. The only attempt, that we are aware of, to describe a combinatorial algorithm for the maximum L-bounded flow problem was done by Koubek and Říha in 1981. Unfortunately, their paper contains substantional flaws and the algorithm does not work; in the first part of this paper, we describe these problems.
In the second part of this paper we describe a combinatorial algorithm based on the exponential length method that finds a -approximation of the maximum L-bounded flow in time where m is the number of edges in the graph. Moreover, we show that this approach works even for the NP-hard generalization of the maximum L-bounded flow problem in which each edge has a length.
Springer