AN EXTENDED PLANAR ALGORITHM FOR MAXIMUM INTEGRAL 2-FLOW

Authors
MANOR R PENN M
Citation
R. Manor et M. Penn, AN EXTENDED PLANAR ALGORITHM FOR MAXIMUM INTEGRAL 2-FLOW, Networks, 32(1), 1998, pp. 67-76
Citations number
20
Categorie Soggetti
Computer Science Hardware & Architecture","Computer Science Hardware & Architecture
Journal title
Networks → ACNP
ISSN journal
00283045
Volume
32
Issue
1
Year of publication
1998
Pages
67 - 76
Database
ISI
SICI code
0028-3045(1998)32:1<67:AEPAFM>2.0.ZU;2-E
Abstract
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 i n planar graphs to certain undirected K-3,K-3-free graphs (graphs not containing any subgraph homeomorphic to K-3,K-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. (C ) 1998 John Wiley & Sons, Inc. Networks 32: 67-76, 1998.