Garg, Naveen ; Vazirani, Vijay V. ; Yannakakis, Mihalis (2004) Multiway cuts in directed and node weighted graphs Journal of Algorithms, 50 (1). pp. 49-61. ISSN 0196-6774
Full text not available from this repository.
Official URL: http://www.sciencedirect.com/science/article/pii/S...
Related URL: http://dx.doi.org/10.1016/S0196-6774(03)00111-1
Abstract
A (2−2/k) approximation algorithm is presented for the node multiway cut problem, thus matching the result of Dahlhaus et al. (SIAM J. Comput. 23 (4) (1994) 864–894) for the edge version of this problem. This is done by showing that the associated LP-relaxation always has a half-integral optimal solution.
| Item Type: | Article |
|---|---|
| Source: | Copyright of this article belongs to Elsevier Science. |
| ID Code: | 101263 |
| Deposited On: | 31 Jan 2018 09:10 |
| Last Modified: | 31 Jan 2018 09:10 |
Repository Staff Only: item control page
