A fast algorithm for finding a maximum free multiflow in an inner Eulerian network and some generalizatons
type: Item
instance of: scholarly article
title: A fast algorithm for finding a maximum free multiflow in an inner Eulerian network and some generalizatons
zbMATH Open document ID: 0914.90110
DOI: 10.1007/PL00009811
author: Toshihide Ibaraki
author: Hiroshi Nagamochi
author: Alexander V. Karzanov
published in: Combinatorica
publication date: 1999-03-14T00:00:00Z
review text: The paper concerns the problem of finding the maximum flow between two terminals in a network \(N = (G,T,c)\) consisting of an undirected graph \(G=(V_{G'}E_{G'})\), a subset \(T\) of nodes of \(G\), called terminals, and a nonnegative integer - valued function \(c: E_G\to Z_+\) of capacities of edges of \(G\). A free multiflow is a collection of flows between arbitrary pairs of terminals such that total flow through each edge does not exceed its capacity. Special networks \(N\) as inner Eulerian network, laminar locking problem, and inner balanced directed network are defined. The paper presents three algorithms: an algorithm for finding an integer maximum free multiflow in an inner Eulerian network, an algorithm for the laminar locking problem and an algorithm for balanced networks. For each of the proposed algorithms the complexity analysis is given.
Mathematics Subject Classification ID: 90B10
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 90C60
zbMATH DE Number: 1261187
zbMATH Keywords: combinatorial programming
zbMATH Keywords: flows in networks
zbMATH Keywords: inner Eulerian network
reviewed by: Florica Luban
MaRDI profile type: Publication
full work available at URL: pl00009811
OpenAlex ID: W2069968725
description: scientific article; zbMATH DE number 1261187