Romanian Journal of Information Science and Technology (ROMJIST)

An open – access publication

  |  HOME  |   GENERAL INFORMATION  |   ROMJIST ON-LINE  |  KEY INFORMATION FOR AUTHORS  |   COMMITTEES  |  

ROMJIST is a publication of Romanian Academy,
Section for Information Science and Technology

Editor – in – Chief:
Academician Dan Dascalu

Secretariate (office):
Adriana Neagu
Adress for correspondence: romjist@nano-link.net (after 1st of January, 2019)

Editing of the printed version: Mihaela Marian (Publishing House of the Romanian Academy, Bucharest)

Technical editor
of the on-line version:
Lucian Milea (University POLITEHNICA of Bucharest)

Sponsors:
• National Institute for R & D
in Microtechnologies
(IMT Bucharest), www.imt.ro
• Association for Generic
and Industrial Technologies (ASTEGI), www.astegi.ro

ROMJIST Volume 23, No. T, 2020, pp. T18-T27, Paper no. 671/2020
 

Camelia SCHIOPU, Eleonor CIUREA
Maximum Flows in Planar Dynamic Networks. The Static Approach

ABSTRACT: The The research of flows in planar static networks is motivated by the fact that more efficient algorithms can be developed by exploiting the planar structure of the graph. An nontrivial extension of the maximum static flow problem is the maximum dynamic flow model, where the transit time to traverse an arc is taken into consideration. The problem of finding a maximum flow in dynamic network is more complex than the problem of finding a maximum flow in static network. Happily, this complication can be solved by rephrasing the problem from dynamic network D in a multiple source multiple sink static reduced expanded network R_0. If dynamic network D is planar, we show that the network R0 is planar.

KEYWORDS: planar network, dynamic network, maximum flow

Read full text (pdf)






  |  HOME  |   GENERAL INFORMATION  |   ROMJIST ON-LINE  |  KEY INFORMATION FOR AUTHORS  |   COMMITTEES  |