Integer plane multiflows with a mixed number of demands
type: Item
instance of: scholarly article
title: Integer plane multiflows with a mixed number of demands
zbMATH Open document ID: 0798.90044
author: András Sebö
published in: Journal of Combinatorial Theory. Series B
publication date: 1994-05-05T00:00:00Z
review text: We give a polynomial algorithm which decides the integer solvability of multicommodity flow problems where the union of ``capacity-'' and ``demand-edges'' forms a planar graph, and the number of demand edges is bounded by a prefixed integer \(k\). This problem was solved earlier for \(k= 2\) by Seymour and for \(k=3\) by Korach. For \(k=4\) much work has been done by Korach and Newmann. The main result of the present note is a polynomial algorithm that finds such a multiflow or proves that it does not exist, for arbitrary fixed \(k\). Middendorf and Pfeiffer have recently proved that this problem is NP-complete in general (without fixing \(k\)). We actually give a more general polynomial algorithm, namely to decide whether the relation \(\nu(G,T)= \tau(G,T)\) or its weighted generalization holds for the pair \((G,T)\) (where \(G\) is not necessarily planar), provided \(| T|\) is fixed, thus extending Seymour's method and result for \(| T|= 4\).
Mathematics Subject Classification ID: 90B10
Mathematics Subject Classification ID: 90C60
zbMATH DE Number: 562414
zbMATH Keywords: polynomial algorithm
zbMATH Keywords: integer solvability
zbMATH Keywords: multicommodity flow
MaRDI profile type: Publication
full work available at URL: jctb.1993.1062
OpenAlex ID: W2091250471
DOI: 10.1006/JCTB.1993.1062
description: scientific article; zbMATH DE number 562414