Algorithmic Applications of Baur-Strassen’s Theorem

DOI10.1145/2736283zbMath1426.05164arXiv1204.1616MaRDI QIDQ3177733

Harold N. Gabow, Marek Cygan, Piotr Sankowski

Publication date: 2 August 2018

Published in: Journal of the ACM (Search for Journal in Brave)

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

zbMATH Keywords

diameter; radius; shortest cycle; matrix multiplication; maximum weight matchings

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

68Q25: Analysis of algorithms and problem complexity

05C38: Paths and cycles

05C50: Graphs and linear algebra (matrices, eigenvalues, etc.)

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

05C22: Signed and weighted graphs