2026-07-22T21:28:06Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6977 2024-03-06T10:39:15Z ddc:004 open_access

Improved Distance Queries and Cycle Counting by Frobenius Normal Form Sankowski, Piotr Wegrzycki, Karol Frobenius Normal Form Graph Algorithms All Nodes Shortest Cycles 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 O-tilde(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 following problems efficiently. * All Nodes Shortest Cycles - for every node return the length of the shortest cycle containing it. We give an O-tilde(n^omega) algorithm that improves the previous O-tilde(n^((omega + 3)/2)) algorithm for unweighted digraphs. * We show how to compute all D sets of vertices lying on cycles of length c in {1, ..., D} in randomized time O-tilde(n^omega). It improves upon an algorithm by Cygan where algorithm that computes a single set is presented. * We present a functional improvement of distance queries for directed, unweighted graphs. * All Pairs All Walks - we show almost optimal O-tilde(n^3) time algorithm for all walks counting problem. We improve upon the naive O(D n^omega) time algorithm. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Piotr Sankowski and Karol Wegrzycki 2017 Is Part Of LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2017.56 urn:nbn:de:0030-drops-69773 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2017.56 eng https://creativecommons.org/licenses/by/3.0/legalcode