Skip to main content


Weitere Artikel dieser Ausgabe durch Wischen aufrufen

21.11.2018 | Ausgabe 5/2019 Open Access

Theory of Computing Systems 5/2019

Improved Distance Queries and Cycle Counting by Frobenius Normal Form

Theory of Computing Systems > Ausgabe 5/2019
Piotr Sankowski, Karol Węgrzycki
Wichtige Hinweise
Extended Abstract of this paper was presented at STACS 2017 [22]
This article is part of the Topical Collection on Special Issue on Theoretical Aspects of Computer Science (STACS 2017)

Publisher’s Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.


Consider 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 \(\widetilde {O}(n^{\omega })\). 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.

Unsere Produktempfehlungen

Premium-Abo der Gesellschaft für Informatik

Sie erhalten uneingeschränkten Vollzugriff auf alle acht Fachgebiete von Springer Professional und damit auf über 45.000 Fachbücher und ca. 300 Fachzeitschriften.

Über diesen Artikel

Weitere Artikel der Ausgabe 5/2019

Theory of Computing Systems 5/2019 Zur Ausgabe

Premium Partner