Improved distance queries and cycle counting by Frobenius normal form

DOI10.1007/S00224-018-9894-XMaRDI QIDQ2321929zbMATH OpenOpenAlexWikidataFDO

Authors Piotr Sankowski, Karol Węgrzycki

Publication date 27 August 2019

Published in Theory of Computing Systems (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/s00224-018-9894-x

zbMATH Keywords

graph algorithmsFrobenius normal formall-nodes shortest cycles

Mathematics Subject Classification ID

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)

Recommendations

• Improved Distance Queries and Cycle Counting by Frobenius Normal Form
• Algorithmic applications of Baur-Strassen's theorem, shortest cycles, diameter, and matchings
• All-pairs shortest paths for unweighted undirected graphs in o(mn) time
• Finding and counting given length cycles
• Detecting short directed cycles using rectangular matrix multiplication and dynamic programming

Cites work

• scientific article; zbMATH DE number 3138903 (Why is no real title available?)
• scientific article; zbMATH DE number 3651744 (Why is no real title available?)
• scientific article; zbMATH DE number 2081147 (Why is no real title available?)
• scientific article; zbMATH DE number 1744838 (Why is no real title available?)
• scientific article; zbMATH DE number 961607 (Why is no real title available?)
• scientific article; zbMATH DE number 964896 (Why is no real title available?)
• A Theorem on Boolean Matrices
• A shortest cycle for each vertex of a graph
• Algorithmic applications of Baur-Strassen's theorem, shortest cycles, diameter, and matchings
• All pairs shortest paths using bridging sets and rectangular matrix multiplication
• All-pairs shortest paths with a sublinear additive error
• An Upper Bound on the Diameter of a Graph from Eigenvalues Associated with Its Laplacian
• Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs
• Black box Frobenius decompositions over small fields
• Color-coding
• Dynamic Normal Forms and Dynamic Characteristic Polynomial
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Faster all-pairs shortest paths via circuit complexity
• Finding and counting given length cycles
• Finding even cycles even faster
• Fine-grained complexity for sparse graphs
• Improved Distance Queries and Cycle Counting by Frobenius Normal Form
• Minimum Weight Cycles and Triangles: Equivalences and Algorithms
• More algorithms for all-pairs shortest paths in weighted graphs
• On Dynamic Algorithms for Algebraic Problems
• On product of companion matrices
• Powers of tensors and fast matrix multiplication
• Rational solutions of singular linear systems
• Subcubic equivalences between graph centrality problems, APSP and diameter
• Undirected single-source shortest paths with positive integer weights in linear time

Cited in

(2)

• Improved Distance Queries and Cycle Counting by Frobenius Normal Form
• Removing additive structure in 3SUM-based reductions

Describes a project that uses

Uses Software

• Algorithm 97

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)