Thumbnail - Request a copy

Max-multiflow/min-multicut for G+H series-parallel

Cornaz, Denis (2011), Max-multiflow/min-multicut for G+H series-parallel, Discrete Mathematics, 311, 17, p. 1957-1967. http://dx.doi.org/10.1016/j.disc.2011.05.025

Type
Article accepté pour publication ou publié
Date
2011
Journal name
Discrete Mathematics
Volume
311
Number
17
Publisher
Elsevier
Pages
1957-1967
Publication identifier
Metadata
Show full item record
Author(s)
Cornaz, Denis
Abstract (EN)
We give a new characterization of series-parallel graphs which implies that the maximum integer multiflow is equal to the minimum capacity multicut if G + H is series-parallel, where G + H denotes the union of the support graph G and the demand graph H. We investigate the difference between a result of the type ‘‘the cut-condition is sufficient for the existence of a multiflow in some class’’ and a result of the type ‘‘max- multiflow = min-multicut for some class’’.
Subjects / Keywords
Min-max equality; Minimum multicut; Maximum integer multiflow