|
EPrints@IIT Delhi >
Faculty Research Publicatons >
Computer Science and Engineering >
Please use this identifier to cite or link to this item:
http://hdl.handle.net/2074/1332
|
| Title: | Multiway cuts in node weighted graphs |
| Authors: | Garg, Naveen
Vazirani, Vijay V
Yannakakis, Mihalis |
| Keywords: | approximation algorithm
LP-relaxation |
| Issue Date: | 2004 |
| Citation: | Journal of Algorithms, 50(1), 49-61 |
| 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. |
| URI: | http://eprint.iitd.ac.in/dspace/handle/2074/1332 |
| Appears in Collections: | Computer Science and Engineering
|
Files in This Item:
| File |
Description |
Size | Format |
|---|
| gargmul2004.pdf | | 146Kb | Adobe PDF | View/Open |
|
Show full item record
All items in DSpace are protected by copyright, with all rights reserved.
|
