Garg, N. ; Vazirani, V. V. ; Yannakakis, M.
(1997)
*Primal-dual approximation algorithms for integral flow and multicut in trees*
Algorithmica, 18
(1).
pp. 3-20.
ISSN 0178-4617

Full text not available from this repository.

Official URL: http://link.springer.com/article/10.1007%2FBF02523...

Related URL: http://dx.doi.org/10.1007/BF02523685

## Abstract

We study the maximum integral multicommodity flow problem and the minimum multicut problem restricted to trees. This restriction is quite rich and contains as special cases classical optimization problems such as matching and vertex cover for general graphs. It is shown that both the maximum integral multicommodity flow and the minimum multicut problem are NP-hard and MAX SNP-hard on trees, although the maximum integral flow can be computed in polynomial time if the edges have unit capacity. We present an efficient algorithm that computes a multicut and integral flow such that the weight of the multicut is at most twice the value of the flow. This gives a 2-approximation algorithm for minimum multicut and a 1/2-approximation algorithm for maximum integral multicommodity flow in trees.

Item Type: | Article |
---|---|

Source: | Copyright of this article belongs to Springer Verlag. |

Keywords: | Integral Multicommodity Flow; Multicut; Approximation Algorithm; MAX SNP-hard |

ID Code: | 101272 |

Deposited On: | 31 Jan 2018 09:33 |

Last Modified: | 31 Jan 2018 09:33 |

Repository Staff Only: item control page