论文标题
$ f $ f $ factor的多句话的重量尺度算法
A Weight-scaling Algorithm for $f$-factors of Multigraphs
论文作者
论文摘要
我们讨论了组合算法，以在任意多数法纸上找到最大权重$ f $ f $ factor，最多最多$ w $的给定数量级的整体权重。对于简单的双分图，最著名的时间限制为$ O（n^{2/3} \，m \，\ log nw）$（\ cite {gt89}; $ n $和$ m $和$ m $是顶点和边的数量）。 Duan和He等人最近的算法。 \ cite {dhz}对于$ f $ - 简单图的因子出现在此界的对数因子内，$ \ widetilde {o}（n^{2/3} \，m \，\ log w w）$。双方多编码的最著名绑定是$ o（\sqrtφ\，m \，\logφw）$（$φ\ le m $是$ f $ -f $ -factor的大小，$ f $ -factor，$φ= \ sum_ {v \ in v} f（v）f（v）/2 $）。该界限比限制简单图更笼统，甚至在“小”简单图上都优越，即$φ= o（n^{4/3}）$。我们提出了一种算法，该算法出现在此绑定的$ \ sqrt {\logφ} $中，即$ o（\ sqrt {φ\ log或log或mogφ} \，m \，m \，\logφw）$。 对于普通匹配的特殊情况（$ f \ equiv 1 $），该算法是Gabow和Tarjan \ cite {gt}算法的直接概括。我们首先介绍我们的算法，用于普通匹配，因为分析是\ cite {gt}的简化版本。此外，该算法和分析都在没有修改中纳入多编码算法。 为了将这些想法扩展到$ f $ - 因素，第一步是“扩展”边缘（即，用长度3交替的路径代替边缘）。 \ cite {dhz}使用整个图的一次性扩展。我们的算法仅通过扩展选定的边缘来使图形保持较小，并在不再需要时将它们“压缩”回原始源。还需要其他几个想法，包括放松“开花”对e-blossom的概念（“扩展的开花”）。
We discuss combinatorial algorithms for finding a maximum weight $f$-factor on an arbitrary multigraph, for given integral weights of magnitude at most $W$. For simple bipartite graphs the best-known time bound is $O(n^{2/3}\, m\, \log nW)$ (\cite{GT89}; $n$ and $m$ are respectively the number of vertices and edges). A recent algorithm of Duan and He et al. \cite{DHZ} for $f$-factors of simple graphs comes within logarithmic factors of this bound, $\widetilde{O} (n^{2/3}\, m\, \log W)$. The best-known bound for bipartite multigraphs is $O(\sqrt Φ\, m\, \log ΦW)$ ($Φ\le m$ is the size of the $f$-factor, $Φ=\sum_{v\in V}f(v)/2$). This bound is more general than the restriction to simple graphs, and is even superior on "small" simple graphs, i.e., $Φ=o(n^{4/3})$. We present an algorithm that comes within a $\sqrt {\log Φ}$ factor of this bound, i.e., $O(\sqrt {Φ\log Φ}\,m \,\log ΦW)$. The algorithm is a direct generalization of the algorithm of Gabow and Tarjan \cite{GT} for the special case of ordinary matching ($f\equiv 1$). We present our algorithm first for ordinary matching, as the analysis is a simplified version of \cite{GT}. Furthermore the algorithm and analysis both get incorporated without modification into the multigraph algorithm. To extend these ideas to $f$-factors, the first step is "expanding" edges (i.e., replacing an edge by a length 3 alternating path). \cite{DHZ} uses a one-time expansion of the entire graph. Our algorithm keeps the graph small by only expanding selected edges, and "compressing" them back to their original source when no longer needed. Several other ideas are needed, including a relaxation of the notion of "blossom" to e-blossom ("expanded blossom").
