Breaking the O(m2n) Barrier for Minimum Cycle Bases
Breaking the O(m2n) Barrier for Minimum Cycle Bases
复制标题
打破最小周期基数的 O(m2n) 障碍
DOI：
--
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
Romeo Rizzi
中科院分区：
文献类型：
--
作者：
E. Amaldi;Claudio Iuliano;Tomasz Jurkiewicz;K. Mehlhorn;Romeo Rizzi
给出了图的最小有向和无向圈基的构造算法。对于一般图，新算法是MonteCarlo算法，其运行时间为O（m ω），其中ω是矩阵乘法的指数。以前的最佳算法的运行时间（{ ilde{O}}（m^2n））。对于平面图，新算法是确定性的，运行时间为O（n2）.最好的算法的运行时间为O（n2 logn）.我们改进运行时间的一个关键因素是，搜索最小的基地可以限制在一组总长度为O（nm）的候选周期。
We give improved algorithms for constructing minimum directed and undirected cycle bases in graphs. For general graphs, the new algorithms are Monte Carlo and have running time O(m ω ), where ω is the exponent of matrix multiplication. The previous best algorithm had running time ({ ilde{O}}(m^2n)). For planar graphs, the new algorithm is deterministic and has running time O(n 2). The previous best algorithm had running time O(n 2 logn). A key ingredient to our improved running times is the insight that the search for minimum bases can be restricted to a set of candidate cycles of total length O(nm).