CATALOGO DEI PRODOTTI DELLA RICERCA
IRIS è la soluzione IT che facilita la raccolta e la gestione dei dati relativi alle attività e ai prodotti della ricerca. Fornisce a ricercatori, amministratori e valutatori gli strumenti per monitorare i risultati della ricerca, aumentarne la visibilità e allocare in modo efficace le risorse disponibili.
EnglishWe 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).
| Titolo: | Breaking the O(m^2 n) Barrier for Minimum Cycle Bases. |
| Autori: | |
| Data di pubblicazione: | 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). |
| Handle: | http://hdl.handle.net/11562/409548 |
| ISBN: | 9783642041273 |
| Appare nelle tipologie: | 04.01 Contributo in atti di convegno |
File in questo prodotto:
http://hdl.handle.net/11562/409548
Copyright © 2021