Algorithmic trade-offs for girth approximation in undirected graphs
Algorithmic trade-offs for girth approximation in undirected graphs
复制标题
无向图中周长近似的算法权衡
DOI：
10.1137/1.9781611977073.62
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Zwick, Uri
中科院分区：
文献类型：
--
作者：
Kadria, Avi;Roditty, Liam;Sidford, Aaron;Williams, Virginia Vassilevska;Zwick, Uri
我们提出了几个新的有效算法来近似的围长，g，加权和unweightedn-顶点，m-边无向图。对于具有多项式有界、整数、非负边权的无向图，我们给出了一个算法，对于任意整数k ≥ 1，该算法运行时间不超过（m+n1 + 1/klogg），并且返回一个长度不超过2kg的圈.对于无权无向图，我们提出了一个算法，对于每个k ≥ 1，运行intimate（n1 + 1/k）时间，并返回一个长度至多为2k[g/2]的圈，几乎k-近似。这两种算法都提供了运行时间和近似质量之间的权衡。我们还获得了近似因子优于2的更快算法，以及当围长为奇数或小时（例如，第3和第4段）。
We present several new efficient algorithms for approximating the girth,g, of weighted and unweightedn-vertex,m-edge undirected graphs. For undirected graphs with polynomially bounded, integer, non-negative edge weights, we provide an algorithm that for every integerk≥ 1, runs inÕ(m+n1 + 1/klogg) time and returns a cycle of length at most 2kg. For unweighted, undirected graphs we present an algorithm that for everyk≥ 1, runs inÕ(n1 + 1/k) time and returns a cycle of length at most 2k[g/2], an almostk-approximation. Both algorithms provide trade-offs between the running time and the quality of the approximation. We also obtain faster algorithms for approximation factors better than 2, and improved approximations when the girth is odd or small (e.g., 3 and 4).