✦ LIBER ✦

An extended planar algorithm for maximum integral two-flow

✍ Scribed by Manor, Raanan; Penn, Michal

Publisher: John Wiley and Sons
Year: 1998
Tongue: English
Weight: 170 KB
Volume: 32
Category: Article
ISSN: 0028-3045
DOI: 10.1002/(sici)1097-0037(199808)32:1<67::aid-net5>3.0.co;2-h

No coin nor oath required. For personal study only.

✦ Synopsis

Several problems, including the maximum integral two-flow problem, are known to be NPcomplete, but efficiently solvable for planar graphs. In this paper, we extend the algorithm for maximum integral two-flow in planar graphs to certain undirected K 3,3 -free graphs (graphs not containing any subgraph homeomorphic to K 3,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.

📜 SIMILAR VOLUMES

An exact algorithm for the batch sequenc

An exact algorithm for the batch sequencing problem in a two-machine flow shop with limited buffer

✍ A. Agnetis; F. Rossi; G. Gristina 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 295 KB 👁 2 views

This paper deals with the problem of makespan minimization in a flow shop with two machines when the input buffer of the second machine can only host a limited number of parts. Here we analyze the problem in the context of batch processing, i.e., when identical parts must be processed consecutively.