Skip to main content
main-content

Tipp

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

Zeitschrift:
Theory of Computing Systems > Ausgabe 5/2019
Autoren:
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.

Abstract

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.

Literatur
Über diesen Artikel

Weitere Artikel der Ausgabe 5/2019

Theory of Computing Systems 5/2019 Zur Ausgabe

Premium Partner

    Bildnachweise