Artykuł w czasopiśmie
Brak miniatury
Licencja
ClosedAccessDostęp zamknięty
 

Improved Distance Queries and Cycle Counting by Frobenius Normal Form

Uproszczony widok
cris.lastimport.scopus2024-02-12T20:28:31Z
dc.abstract.enConsider an unweighted, directed graph G with the diameter D. In this paper, we introduce the framework for counting cycles and walks of given length in matrix multiplication time O\textasciitilde(n$ω$)\$\backslashwidetilde \O(n^\backslashomega )\$. The framework is based on the fast decomposition into Frobenius normal form and the Hankel matrix-vector multiplication. It allows us to solve the All-Nodes Shortest Cycles, All-Pairs All Walks problems efficiently and also give some improvement upon distance queries in unweighted graphs.
dc.affiliationUniwersytet Warszawski
dc.contributor.authorWęgrzycki, Karol
dc.contributor.authorSankowski, Piotr
dc.date.accessioned2024-01-25T03:58:44Z
dc.date.available2024-01-25T03:58:44Z
dc.date.issued2019
dc.description.financeNie dotyczy
dc.description.number5
dc.description.volume63
dc.identifier.doi10.1007/S00224-018-9894-X
dc.identifier.issn1432-4350
dc.identifier.urihttps://repozytorium.uw.edu.pl//handle/item/109099
dc.identifier.weblinkhttps://link.springer.com/article/10.1007%2Fs00224-018-9894-x
dc.languageeng
dc.pbn.affiliationcomputer and information sciences
dc.relation.ispartofTheory of Computing Systems
dc.relation.pages1049–1067
dc.rightsClosedAccess
dc.sciencecloudnosend
dc.titleImproved Distance Queries and Cycle Counting by Frobenius Normal Form
dc.typeJournalArticle
dspace.entity.typePublication