期刊
INFORMATION PROCESSING LETTERS
卷 97, 期 4, 页码 156-160出版社
ELSEVIER
DOI: 10.1016/j.ipl.2005.10.005
关键词
approximation algorithms; directed graphs; sparsest cut; multicommodity flow
We give an O (root n)-approximation algorithm for the Sparsest Cut Problem on directed graphs. A naive reduction from Sparsest Cut to Minimum Multicut would only give an approximation ratio of O(root n log D), where D is the sum of the demands. We obtain the improvement using a novel LP-rounding method for fractional Sparsest Cut, the dual of Maximum Concurrent Flow. (c) 2005 Elsevier B.V. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据