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).
9783642041273
minimum cycle basis; cycle space; randomized algorithm; Monte Carlo algorithm; planar graphs
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11562/409548
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 17
  • ???jsp.display-item.citation.isi??? 14
social impact