Improved distance queries and cycle counting by Frobenius normal form
DOI10.1007/S00224-018-9894-XzbMATH Open1427.90285OpenAlexW2900560911WikidataQ92510040 ScholiaQ92510040MaRDI QIDQ2321929FDOQ2321929
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) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Powers of tensors and fast matrix multiplication
- A Theorem on Boolean Matrices
- All pairs shortest paths using bridging sets and rectangular matrix multiplication
- Fast Probabilistic Algorithms for Verification of Polynomial Identities
- Color-coding
- Minimum Weight Cycles and Triangles: Equivalences and Algorithms
- Finding and counting given length cycles
- More algorithms for all-pairs shortest paths in weighted graphs
- Faster all-pairs shortest paths via circuit complexity
- An Upper Bound on the Diameter of a Graph from Eigenvalues Associated with Its Laplacian
- Undirected single-source shortest paths with positive integer weights in linear time
- Rational solutions of singular linear systems
- On product of companion matrices
- Subcubic Equivalences Between Graph Centrality Problems, APSP and Diameter
- Algorithmic Applications of Baur-Strassen’s Theorem
- Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs
- Dynamic Normal Forms and Dynamic Characteristic Polynomial
- All-pairs shortest paths with a sublinear additive error
- Black box Frobenius decompositions over small fields
- On Dynamic Algorithms for Algebraic Problems
- A shortest cycle for each vertex of a graph
- Fine-grained complexity for sparse graphs
- Finding even cycles even faster
- Improved Distance Queries and Cycle Counting by Frobenius Normal Form
Cited In (2)
Uses Software
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 Q2321929)
