An Algorithm for Constructing a Hereditarily Minimax Network with Predefined Vector of Node Degrees

In contrast to the classical transportation problem, where supply and demand points are known, and it is required to minimize the transportation cost, we consider a minimax criterion. In particular, a matrix with the minimal largest element is sought in the class of nonnegative matrices with given sums of row and column elements. In this case, the concept of the minimax criterion can be interpreted as follows. Suppose that the shipment time from a supply point to a demand point is proportional to the amount to be shipped. Then, the minimax is the minimal time required to transport the total amount. It is a common situation that the decision maker does not know the tariff coefficients. In other situations, they do not have any meaning, and neither do nonlinear tariff objective functions. In such cases, the minimax interpretation leads to an effective solution. For the classes of undirected networks with predefined vector of node degrees (transport and network polyhedrons) by using a characteristic functions the analytical formulas of calculating the minimax values expressed in terms of the vector coordinates and a nonnegative parameter are obtained. The minimax values determine the necessary and sufficient conditions under which the truncated polyhedrons are not empty sets. Finally, we obtained an algorithm for constructing a hereditarily-minimax network in network polyhedrons.

References

[1] Cormen T., Leiserson Ch., Rivest R., Stein C. Introduction to algorithms. 3rd Edition. MIT Press, 2009.

[2] Zykov A.A. Osnovy teorii grafov [Fundamentals of graph theory]. Moscow, Vuzovskaya kniga, 2004. 664 p.

[3] Mironov A.A., Tsurkov V.I. Hereditarily minimax matrices in models of transportation type. Journal of Computer and Systems Sciences International, 1998, vol. 37, no. 6, pp. 927-944.

[4] Mironov A.A., Tsurkov V.I. Open transportation models with a minimax criterion. Dokl. Math., 2001, vol. 64 (3), pp. 374-377.

[5] Tsurkov V., Mironov A. Minimax under transportation constrains. Dordrecht-Boston-London, Kluwer Academic Publishers, 1999.

[6] Lukoyanov N.Yu. Minimax and viscosity solutions in optimization problems for hereditary systems. Proc. Steklov Inst. Math., 2010, vol. 269, pp. 214-225. DOI: 10.1134/S0081543810060179

[7] Holstein E.G., Yudin D.B. Zadachi lineynogo programmirovaniya transportnogo tipa [Linear programming problem of the transport type]. Moscow, Nauka Publ., 1969. 382 p.

[8] Goldsmith A. Wireless communications. Cambridge University Press, 2005. 571 p.

[9] Lewis F.L. Wireless sensor networks. Smart Environments: Technologies, Protocols, and Applications. N.Y., John Wiley, 2004. 432 p.

[10] Tishchenko S.A. Separators in planar graphs as a new characterization tool. Fundam. Prikl. Mat., 2002, vol. 8, no. 4, pp. 1193-1214 (in Russ.).

[11] Voloshin V.I. Introduction to graph and hypergraph theory. N.Y., Nova Science Publishers, 2009.

[12] Selin P.S., Tsurkov V.I. Method of characteristic functions for classes of networks with fixed node degrees. Journal of Computer and Systems Sciences International, 2014, vol. 53, no. 5, pp. 645-655. DOI: 10.1134/S1064230714050128

[13] Ding J., Tana P., Lu Y.-Z. Optimizing the controllability index of directed networks with the fixed number of control nodes. Neurocomputing, 2016, vol. 171, pp. 1524-1532.

[14] Fontanari J.F., Rodrigues F.A. Influence of network topology on cooperative problemsolving systems. Theory in Biosciences, 2015, pp. 1-10.

[15] Peng G.-S., Wu J. Optimal network topology for structural robustness based on natural connectivity. Physica A: Statistical Mechanics and its Applications, 2016, vol. 443, pp. 212-220. Available at: http://dx.doi.org/10.1016/j.physa.2015.09.023

[16] Abello J., Queyroi F. Network decomposition into fixed points of degree peeling. Social Network Analysis and Mining, 2014, no. 4, pp. 191.

[17] Horvat E.-A., Zweig K.A. A fixed degree sequence model for the one-mode projection of multiplex bipartite graphs. Social Network Analysis and Mining, 2013, vol. 3, no. 4, pp. 12091224.

[18] Dong G., Gao J., Du R., Tian L., Stanley H.E., Havlin S. Robustness of network of networks under targeted attack. Physical Review E, 2013, vol. 87, no. 5, pp. 052804-1-052804-11. DOI: 10.1103/PhysRevE.87.052804

[19] Richard M.G.A., Fanchon E. Reduction and fixed points of Boolean networks and linear network coding solvability. IEEE Transactions on Information Theory, 2016, vol. 62, no. 5, pp. 2504-2519.

[20] Nazarov M.N. On the representation of graphs in the form of a special type of binary algebra. Prikl. Diskr. Mat., 2015, no. 1, pp. 96-104.