Improved distance queries and cycle counting by Frobenius normal form
From MaRDI portal
Publication:2321929
DOI10.1007/s00224-018-9894-xzbMath1427.90285OpenAlexW2900560911WikidataQ92510040 ScholiaQ92510040MaRDI QIDQ2321929
Piotr Sankowski, Karol Węgrzycki
Publication date: 27 August 2019
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00224-018-9894-x
Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)
Uses Software
Cites Work
- On product of companion matrices
- Finding and counting given length cycles
- A shortest cycle for each vertex of a graph
- On Dynamic Algorithms for Algebraic Problems
- Undirected single-source shortest paths with positive integer weights in linear time
- Algorithmic Applications of Baur-Strassen’s Theorem
- All-pairs shortest paths with a sublinear additive error
- Powers of tensors and fast matrix multiplication
- Black box Frobenius decompositions over small fields
- Rational solutions of singular linear systems
- All pairs shortest paths using bridging sets and rectangular matrix multiplication
- Dynamic Normal Forms and Dynamic Characteristic Polynomial
- More algorithms for all-pairs shortest paths in weighted graphs
- Fast Probabilistic Algorithms for Verification of Polynomial Identities
- An Upper Bound on the Diameter of a Graph from Eigenvalues Associated with Its Laplacian
- Color-coding
- Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs
- Finding even cycles even faster
- Improved Distance Queries and Cycle Counting by Frobenius Normal Form
- Fine-grained complexity for sparse graphs
- Faster all-pairs shortest paths via circuit complexity
- Subcubic Equivalences Between Graph Centrality Problems, APSP and Diameter
- Minimum Weight Cycles and Triangles: Equivalences and Algorithms
- A Theorem on Boolean Matrices
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Improved distance queries and cycle counting by Frobenius normal form
