Half-integral flows in a planar graph with four holes (Q1842657): Difference between revisions
From MaRDI portal
Removed claims |
ReferenceBot (talk | contribs) Changed an Item |
||
(2 intermediate revisions by 2 users not shown) | |||
Property / author | |||
Property / author: Alexander V. Karzanov / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Stelian Mihalas / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Paths and metrics in a planar graph with three or more holes. I: Metrics / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Paths and metrics in a planar graph with three or more holes. II: Paths / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3856789 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Multicommodity flows in graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Multicommodity flows in planar graphs / rank | |||
Normal rank |
Latest revision as of 13:15, 23 May 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Half-integral flows in a planar graph with four holes |
scientific article |
Statements
Half-integral flows in a planar graph with four holes (English)
0 references
5 June 1996
0 references
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.
0 references
planar graph
0 references
integral flow
0 references
holes
0 references
eulerian
0 references
multiflow
0 references
paths
0 references