The problem of finding the maximal multiple flow in the divisible network and its special cases

A. V. Smirnov

Modelirovanie i analiz informacionnyh sistem, Tome 22 (2015) no. 4, pp. 533-545.

Résumé

In the article the problem of finding the maximal multiple flow in the network of any natural multiplicity $k$ is studied. There are arcs of three types: ordinary arcs, multiple arcs and multi-arcs. Each multiple and multi-arc is a union of $k$ linked arcs, which are adjusted with each other. The network constructing rules are described. The definitions of a divisible network and some associated subjects are stated. The important property of the divisible network is that every divisible network can be partitioned into $k$ parts, which are adjusted on the linked arcs of each multiple and multi-arc. Each part is the ordinary transportation network. The main results of the article are the following subclasses of the problem of finding the maximal multiple flow in the divisible network. The divisible networks with the multi-arc constraints. Assume that only one vertex is the ending vertex for a multi-arc in $k-1$ network parts. In this case the problem can be solved in a polynomial time. The divisible networks with the weak multi-arc constraints. Assume that only one vertex is the ending vertex for a multi-arc in $s$ network parts ($1\leq s$) and other parts have at least two such vertices. In that case the multiplicity of the multiple flow problem can be decreased to $k-s$. The divisible network of the parallel structure. Assume that the divisible network component, which consists of all multiple arcs, can be partitioned into subcomponents, each of them containing exactly one vertex-beginning of a multi-arc. Suppose that intersection of each pair of subcomponents is the only vertex-network source $x_0$. If $k=2$, the maximal flow problem can be solved in a polynomial time. If $k\geq3$, the problem is $NP$-complete. The algorithms for each polynomial subclass are suggested. Also, the multiplicity decreasing algorithm for the divisible network with weak multi-arc constraints is formulated.

Détail

Keywords: multiple networks, multiple flows, divisible networks, $NP$-completeness
Mots-clés : polynomial algorithm.

Bibliographie

[1] Rublev V. S., Smirnov A. V., “Flows in Multiple Networks”, Yaroslavsky Pedagogichesky Vestnik, 3:2 (2011), 60–68 (in Russian)

[2] Ford L. R., Fulkerson D. R., Flows in Networks, Princeton University Press, 1962 | MR | Zbl

[3] Papadimitriou Ch. H., Steigliz K., Combinatorial Optimization: Algorithms and Complexity, Prentice Hall, 1982 | MR | Zbl

[4] Roublev V. S., Smirnov A. V., “The Problem of Integer-Valued Balancing of a Three-Dimensional Matrix and Algorithms of Its Solution”, Modeling and Analysis of Information Systems, 17:2 (2010), 72–98 (in Russian)

[5] Smirnov A. V., “Some Solvability Classes for The Problem of Integer Balancing of a Three-dimensional Matrix with Constraints of Second Type”, Modeling and Analysis of Information Systems, 20:2 (2013), 54–69 (in Russian)

[6] Smirnov A. V., “Some Solvability Classes for the Problem of Integer Balancing of a Three-Dimensional Matrix with Constraints of the Second Type”, Automatic Control and Computer Sciences, 48:7 (2014), 543–553 | DOI

[7] Korbut A. A., Finkelstein J. J., Diskretnoe programmirovanie, Nauka, 1969 (in Russian) | MR

[8] Raskin L. G., Kirichenko I. O., Mnogoindeksnye zadachi lineynogo programmirovaniya, Radio i svyaz, 1982 (in Russian) | MR

[9] Spieksma F. C. R., “Multi index assignment problems: complexity, approximation, applications”, Nonlinear Assignment Problems. Algorithms and Applications, eds. P. M. Pardalos, L. S. Pitsoulis, Kluwer Academic Publishers, 2000, 1–11 | DOI | MR

[10] Afraimovich L. G., “Three-index linear programs with nested structure”, Automation and Remote Control, 72:8 (2011), 1679–1689 | DOI | MR | Zbl

[11] Kondakov A. S., Roublev V. S., “Zadacha sbalansirovaniya matritsy plana”, Doklady Odesskogo seminara po diskretnoy matematike, 2, Astroprint, 2005, 24–26 (in Russian)

[12] Korshunova N. M., Roublev V. S., “Zadacha tselochislennogo sbalansirovaniya matritsy”, Sovremennye problemy matematiki i informatiki, 3, Yaroslavl State University, 2000, 145–150 (in Russian)

[13] Smirnov A. V., “The Problem of Integer-valued Balancing of a Three-dimensional Matrix and Network Model”, Modeling and Analysis of Information Systems, 16:3 (2009), 70–76 (in Russian)

[14] Afraimovich L. G., Prilutskii M. Kh., “Multiindex resource distributions for hierarchical systems”, Automation and Remote Control, 67:6 (2006), 1007–1016 | DOI | MR | Zbl

[15] Afraimovich L. G., Prilutskii M. Kh., “Multicommodity flows in tree-like networks”, Journal of Computer and Systems Sciences International, 47:2 (2008), 214–220 | DOI | MR | Zbl

[16] Hoffman A. J., Kruskal J. B., “Integral Boundary Points of Convex Polyhedra”, Linear Inequalities and Related Systems, eds. H. W. Kuhn, A. W. Tucker, Princeton University Press, 1972, 223–246 | MR

[17] Roublev V. S., Smirnov A. V., “$NP$-Completeness of the Integer Balancing Problem for a Three-Dimensional Matrix”, Doklady Mathematics, 82:3 (2010), 912–914 | DOI | MR | Zbl

[18] Smirnov A. V., “Nekotorye polinomialnye podklassy zadachi o naibolshem kratnom potoke v delimoy seti”, Discrete Models in Control Systems Theory, IX International Conference: Proceedings, MAKS Press, 2015, 229–231 (in Russian)

[19] Garey M. R., Johnson D. S., Computers and Intractability: A Guide to the Theory of $NP$-Completeness, W. H. Freeman, 1979 | MR | Zbl

[20] Karp R., “Reducibility among combinatorial problems”, Complexity of Computer Computations, eds. R. E. Miller, J. W. Thatcher, Plenum, 1972, 85–103 | DOI | MR