Half-integral flows in a planar graph with four holes

Half-integral flows in a planar graph with four holes

0.00 Avg rating0 Votes
Article ID: iaor1996285
Country: Netherlands
Volume: 56
Issue: 2/3
Start Page Number: 267
End Page Number: 295
Publication Date: Jan 1995
Journal: Discrete Applied Mathematics
Authors:
Keywords: networks: flow
Abstract:

Suppose that equ1 s a planar graph embedded in the conclusion plane, that I, J, K, O are four of its faces (called holes in G), that equ2 equ3 are vertices of G such that each pair equ4 belongs to the boundary of some of I, J, K, O, and that the graph equ5 is eulerian. The paper proves that if the multi(commodity)flow problem in G with unit demands on the values of flows from equ6 to equ7 equ8 has a solution then it has a half-integral solution as well. In other words, there exist paths equ9 in G such that each equ10 connects equ11 and equ12, and each edge of G is covered at most twice by these paths. (It is known that in case of at most three-holes there exist edge-disjoint paths connecting equ13 and equ14,equ15, provided that the corresponding multiflow problem has a solution, but this is, in general, false in case of four holes.)

Reviews

Required fields are marked *. Your email address will not be published.