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., 2015, Volume 22, Number 4, Pages 533–545 (Mi mais458)  

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

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

A. V. Smirnov

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

Abstract: 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<k-1$) 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.

Keywords: multiple networks, multiple flows, divisible networks, $NP$-completeness, polynomial algorithm.

Funding Agency Grant Number
Russian Foundation for Basic Research 15-07-03038 A


DOI: https://doi.org/10.18255/1818-1015-2015-4-533-545

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

Bibliographic databases:

UDC: 519.179.2, 519.854.3
Received: 10.07.2015

Citation: A. V. Smirnov, “The problem of finding the maximal multiple flow in the divisible network and its special cases”, Model. Anal. Inform. Sist., 22:4 (2015), 533–545

Citation in format AMSBIB
\Bibitem{Smi15}
\by A.~V.~Smirnov
\paper The problem of finding the maximal multiple flow in the divisible network and its special cases
\jour Model. Anal. Inform. Sist.
\yr 2015
\vol 22
\issue 4
\pages 533--545
\mathnet{http://mi.mathnet.ru/mais458}
\crossref{https://doi.org/10.18255/1818-1015-2015-4-533-545}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=3418472}
\elib{http://elibrary.ru/item.asp?id=24273053}


Linking options:
  • http://mi.mathnet.ru/eng/mais458
  • http://mi.mathnet.ru/eng/mais/v22/i4/p533

    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, “Setevaya model dlya zadachi tselochislennogo sbalansirovaniya chetyrekhmernoi matritsy”, Model. i analiz inform. sistem, 23:4 (2016), 466–478  mathnet  crossref  mathscinet  elib
  • Моделирование и анализ информационных систем
    Number of views:
    This page:130
    Full text:34
    References:18

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