|
|||||
|
|
Packing and covering with integral feasible flows in integral supply-demand networks |
|
| Authors: | R. E. Bixby O. M. -C. Marcotte L. E. Trotter Jr. |
| Affiliation: | (1) Department of Mathematical Sciences, Rice University, Houston, TX, USA;(2) Département de mathématiques et d'informatique, Université du Québec à Montréal, Montréal, Canada;(3) School of OR&IE, Cornell University, Ithaca, NY, USA |
| Abstract: | Polynomial-time algorithms are presented for solving combinatorial packing and covering problems defined from the integral feasible flows in an integral supply-demand network. These algorithms are also shown to apply to packing and covering problems defined by the minimal integral solutions to general totally unimodular systems. Analogous problems arising from matroid bases are also discussed and it is demonstrated that a means for solving such problems is provided by recent work of Cunningham. |
| Keywords: | Network flows covering and packing polynomial-time algorithm |
| 本文献已被 SpringerLink 等数据库收录！ | |