Improved Distance Queries and Cycle Counting by Frobenius Normal Form

DOI10.4230/LIPICS.STACS.2017.56zbMATH Open1402.68107arXiv1611.03789OpenAlexW3100962231MaRDI QIDQ4636657FDOQ4636657

Authors: Piotr Sankowski, Karol Węgrzycki 

Publication date: 19 April 2018

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 $widetildeO(n^{o}mega)$. 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.

Full work available at URL: https://arxiv.org/abs/1611.03789

Recommendations

• Improved distance queries and cycle counting by Frobenius normal form
• Improved distance queries in planar graphs
• A cycle-based formulation for the distance geometry problem
• Approximate distance oracles with improved query time
• Approximate Distance Queries in Disk Graphs
• An improved approximation algorithm for the discrete Fréchet distance
• Cycle-based formulations in distance geometry

zbMATH Keywords

graph algorithmsFrobenius normal formall-nodes shortest cycles

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Enumeration in graph theory (05C30) Paths and cycles (05C38)

Cited In (2)

• Improved distance queries and cycle counting by Frobenius normal form
• Improved time bounds for all pairs non-decreasing paths in general digraphs

This page was built for publication: Improved Distance Queries and Cycle Counting by Frobenius Normal Form

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4636657)