RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Model. Anal. Inform. Sist.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Model. Anal. Inform. Sist., 2016, Volume 23, Number 4, Pages 466–478 (Mi mais515)  

This article is cited in 1 scientific paper (total in 1 paper)

Network model for the problem of integer balancing of a four-dimensional matrix

A. V. Smirnov

P.G. Demidov Yaroslavl State University, Sovetskaya str., 14, Yaroslavl, 150000, Russia

Abstract: The problem of integer balancing of a four-dimensional matrix is studied. The elements of the inner part (all four indices are greater than zero) of the given real matrix are summed in each direction and each two- and three-dimensional section of the matrix; the total sum is also found. These sums are placed into the elements where one or more indices are equal to zero (according to the summing directions). The problem is to find an integer matrix of the same structure, which can be produced from the initial one by replacing the elements with the largest previous or the smallest following integer. At the same time, the element with four zero indices should be produced with standard rules of rounding-off. In the article the problem of finding the maximum multiple flow in the network of any natural multiplicity $k$ is also 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. There are defined the basic principles for reducing the integer balancing problem of an $l$-dimensional matrix ($l\geq3$) to the problem of finding the maximum flow in a divisible multiple network of multiplicity $k$. There are stated the rules for reducing the four-dimensional balancing problem to the maximum flow problem in the network of multiplicity 5. The algorithm of finding the maximum flow, which meets the solvability conditions for the integer balancing problem, is formulated for such a network.

Keywords: integer balancing, multiple networks, multiple flows, divisible networks, $NP$-completeness, generalized labeling algorithm, four-dimensional matrices.

DOI: https://doi.org/10.18255/1818-1015-2016-4-466-478

Full text: PDF file (572 kB)
References: PDF file   HTML file

Bibliographic databases:

UDC: 519.179.2, 519.854.3
Received: 18.04.2016

Citation: A. V. Smirnov, “Network model for the problem of integer balancing of a four-dimensional matrix”, Model. Anal. Inform. Sist., 23:4 (2016), 466–478

Citation in format AMSBIB
\Bibitem{Smi16}
\by A.~V.~Smirnov
\paper Network model for the problem of integer balancing of a four-dimensional matrix
\jour Model. Anal. Inform. Sist.
\yr 2016
\vol 23
\issue 4
\pages 466--478
\mathnet{http://mi.mathnet.ru/mais515}
\crossref{https://doi.org/10.18255/1818-1015-2016-4-466-478}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=3549347}
\elib{http://elibrary.ru/item.asp?id=26561564}


Linking options:
  • http://mi.mathnet.ru/eng/mais515
  • http://mi.mathnet.ru/eng/mais/v23/i4/p466

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    This publication is cited in the following articles:
    1. A. V. Smirnov, “Zadacha o kratchaishem puti v kratnom grafe”, Model. i analiz inform. sistem, 24:6 (2017), 788–801  mathnet  crossref  elib
  • Моделирование и анализ информационных систем
    Number of views:
    This page:90
    Full text:24
    References:14

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2020