论文标题
通过切割平衡对有向图的稀疏
Sparsification of Directed Graphs via Cut Balance
论文作者
论文摘要
在本文中，我们考虑了针对有向图的切割稀疏器和草图的问题。为了绕过已知的下限，我们允许Sparsifier/Sketch取决于输入图的平衡，该图形平滑地插入了无向图和有向图之间。我们给出了几乎匹配的上限和下限（参见Benczúr和Karger，STOC，1996年）和EAPH（Andoni等人，ITCS 2016），将Sparsifiers/Shuppifiers/Shuppifiers/Shuptes cut sparsifiers/Shuptes作为切割平衡的函数，定义了有指导图的两个方向（Ene et e et eT et eet et e et et e et eT and）的最大值比率。我们还通过使用削减平衡来显示出有趣的挖掘稀疏性应用程序，以提供非常简短的证明Karger和Levine的最大流量结果（Stoc 2002）。
In this paper, we consider the problem of designing cut sparsifiers and sketches for directed graphs. To bypass known lower bounds, we allow the sparsifier/sketch to depend on the balance of the input graph, which smoothly interpolates between undirected and directed graphs. We give nearly matching upper and lower bounds for both for-all (cf. Benczúr and Karger, STOC 1996) and for-each (Andoni et al., ITCS 2016) cut sparsifiers/sketches as a function of cut balance, defined the maximum ratio of the cut value in the two directions of a directed graph (Ene et al., STOC 2016). We also show an interesting application of digraph sparsification via cut balance by using it to give a very short proof of a celebrated maximum flow result of Karger and Levine (STOC 2002).
