论文标题
在低建立图中匹配大小的估计器与两个应用
An Estimator for Matching Size in Low Arboricity Graphs with Two Applications
论文作者
论文摘要
在本文中，我们提出了一个新的基于简单学位的估计量，该估计量对于有界的树木图中的最大匹配大小。当图形的树木由$α$界定时，估计器给出了$α+2 $ tage因子的匹配大小的近似。对于平面图，我们显示估计器的功能更好，并返回匹配大小的$ 3.5 $近似值。 使用此估计器，我们将获得新的结果，以近似计算的流和分布式模型中平面图的匹配大小。特别是，在顶点 - arrival流中，我们获得了一个随机$ o（\ frac {\ sqrt {n}} {ε^2} \ log n）$ space算法，用于近似于$（3.5+ε）$在$ n $ n $ vertices上的$（3.5+ε）$ factor $（3.5+ε）$内的匹配大小。同样，我们使用$ o（\ frac {n^{2/3}} {n^{2/3}} {ε^2} \ log log n）$ communication在$（3.5+ε）$ factor $（3.5+ε）$因子内近似匹配大小的同时协议。 与先前的估计器相比，本文中的估计器不需要知道输入图的树木性，而是改善了平面图情况的近似因素。
In this paper, we present a new simple degree-based estimator for the size of maximum matching in bounded arboricity graphs. When the arboricity of the graph is bounded by $α$, the estimator gives a $α+2$ factor approximation of the matching size. For planar graphs, we show the estimator does better and returns a $3.5$ approximation of the matching size. Using this estimator, we get new results for approximating the matching size of planar graphs in the streaming and distributed models of computation. In particular, in the vertex-arrival streams, we get a randomized $O(\frac{\sqrt{n}}{ε^2}\log n)$ space algorithm for approximating the matching size within $(3.5+ε)$ factor in a planar graph on $n$ vertices. Similarly, we get a simultaneous protocol in the vertex-partition model for approximating the matching size within $(3.5+ε)$ factor using $O(\frac{n^{2/3}}{ε^2}\log n)$ communication from each player. In comparison with the previous estimators, the estimator in this paper does not need to know the arboricity of the input graph and improves the approximation factor for the case of planar graphs.
