An extended planar algorithm for maximum integral two-flow
Raanan Manor, Michal Penn · Networks · 1998
Several problems, including the maximum integral two-flow problem, are known to be NP-complete, but efficiently solvable for planar graphs. In this paper, we extend the algorithm for maximum integral two-flow in planar graphs to certain undirected K3,3-free graphs (graphs not containing any subgraph homeomorphic to K3,3). For such graphs, we provide an O(n) algorithm for determining a maximum integral two-flow of a value not less than the value of a maximum two-flow minus two. © 1998 John Wiley & Sons, Inc. Networks 32: 67–76, 1998