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 O(m^2 n). 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 log n). 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).
Breaking the O(m^2 n) Barrier for Minimum Cycle Bases.
RIZZI, ROMEO
2009
Abstract
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 O(m^2 n). 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 log n). 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).
File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
