论文标题
一般图中的加权$ f $ factor的缩放算法
A Scaling Algorithm for Weighted $f$-Factors in General Graphs
论文作者
论文摘要
我们在任何一般简单的图表上研究最大重量完美$ f $ - 因素问题$ g =（v，e，w）$，具有正面的边缘权重$ w $，$ n = | v | $，$ m = | e | $。当我们有一个函数$ f：v \ rightArrow \ mathbb {n} _+$上的函数时，完美的$ f $ factor是一种概括性匹配，因此每个顶点$ u $均与$ f（u）$不同的边缘匹配。此问题上先前的最佳算法$ O（m f（v））$ [GABOW 2018]或$ \ tilde {o}（w（f（f（v））^{2.373}））$ [Gabow and Sankowski 2013]在本文中，我们为此问题提供了一个缩放算法，用于运行时间$ \ tilde {o}（mn^{2/3} \ log w）$。以前，这种结合仅在两分图中闻名[Gabow and Tarjan 1989]。我们算法的运行时间独立于$ f（v）$，因此它首先打破了大$ f（v）$的$ω（mn）$屏障，即使对于未加权的$ f $ f $ factor问题，总体图中。
We study the maximum weight perfect $f$-factor problem on any general simple graph $G=(V,E,w)$ with positive integral edge weights $w$, and $n=|V|$, $m=|E|$. When we have a function $f:V\rightarrow \mathbb{N}_+$ on vertices, a perfect $f$-factor is a generalized matching so that every vertex $u$ is matched to $f(u)$ different edges. The previous best algorithms on this problem have running time $O(m f(V))$ [Gabow 2018] or $\tilde{O}(W(f(V))^{2.373}))$ [Gabow and Sankowski 2013], where $W$ is the maximum edge weight, and $f(V)=\sum_{u\in V}f(u)$. In this paper, we present a scaling algorithm for this problem with running time $\tilde{O}(mn^{2/3}\log W)$. Previously this bound is only known for bipartite graphs [Gabow and Tarjan 1989]. The running time of our algorithm is independent of $f(V)$, and consequently it first breaks the $Ω(mn)$ barrier for large $f(V)$ even for the unweighted $f$-factor problem in general graphs.
