Half-integral flows in a planar graph with four holes
type: Item
instance of: scholarly article
title: Half-integral flows in a planar graph with four holes
zbMATH Open document ID: 0839.05035
DOI: 10.1016/0166-218X(94)00090-Z
published in: Discrete Applied Mathematics
publication date: 1996-06-05T00:00:00Z
review text: Let \(G= (V, E)\) be a planar, undirected graph; \(I\), \(J\), \(K\), \(O\) four of its faces (called holes in \(G\)) and \(s_1,\dots, s_r, t_1,\dots, t_r\in V\) such that each pair \((r_i, t_i)\) belongs to the boundary of some hole and such that \((V, E\cup \{(s_1, t_1),\dots, (s_r, t_r)\})\) is eulerian. The author proves that if the multiflow problem in \(G\) with unit demand on the values of flow from \(s_i\) to \(t_i\) \((i= 1,\dots, r)\) has a solution, then it has a half-integral solution as well, i.e., there exist paths \(P^1_1,P^2_1,\dots, P^1_r, P^2_r\) in \(G\) such that each \(P^j_i\) connects \(s_i\) and \(t_i\) and each edge of \(G\) is covered at most twice by these paths.
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 90B10
Mathematics Subject Classification ID: 05C45
zbMATH DE Number: 750906
zbMATH Keywords: planar graph
zbMATH Keywords: integral flow
zbMATH Keywords: holes
zbMATH Keywords: eulerian
zbMATH Keywords: multiflow
zbMATH Keywords: paths
author: Alexander V. Karzanov
reviewed by: Stelian Mihalas
MaRDI profile type: Publication
cites work: Paths and metrics in a planar graph with three or more holes. I: Metrics
cites work: Paths and metrics in a planar graph with three or more holes. II: Paths
cites work: Q3856789
cites work: Multicommodity flows in graphs
cites work: Multicommodity flows in planar graphs
description: scientific article; zbMATH DE number 750906