Improved Minimum Cycle Bases Algorithms by Restriction to Isometric Cycles
E. Amaldi, Claudio Iuliano, Tomasz Jurkiewicz, Kurt Mehlhorn, Roméo Rizzi · Max Planck Digital Library · 2011
We present improved algorithms for finding minimum cycle bases in undirected and directed graphs.For general graphs, the new algorithms are Monte Carlo and have running time O(m ω ), where m is the number of edges (arcs) and ω is the exponent of fast matrix multiplication, assuming ω > 2. For planar graphs, the algorithm is deterministic and has running time O(n 2 ), where n is the number of nodes, while the previous best one was O(n 2 log n).We also observe that this algorithm for planar graphs solves the problem for more specialized classes of cycle bases, namely integral, totally unimodular and weakly fundamental cycle bases.A key ingredient to our improved running times is the insight that the search for minimum cycle bases can be restricted to a subset of at most nm candidate cycles, the so-called isometric cycles, whose total number of edges is bounded above by nm.