Algorithmic Applications of Baur-Strassen’s Theorem

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

Harold N. Gabow, Piotr Sankowski, Marek Cygan

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

diameterradiusshortest cyclematrix multiplicationmaximum weight matchings

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Paths and cycles (05C38) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Signed and weighted graphs (05C22)

Related Items (10)

Two dimensional maximum weight matching using Manhattan topology ⋮ NC Algorithms for Weighted Planar Perfect Matching and Related Problems ⋮ Temporal matching on geometric graph data ⋮ Minimum Cuts and Shortest Cycles in Directed Planar Graphs via Noncrossing Shortest Paths ⋮ Improved Time Bounds for All Pairs Non-decreasing Paths in General Digraphs ⋮ A combinatoric interpretation of dual variables for weighted matching and \(f\)-factors ⋮ Temporal matching ⋮ Improved distance queries and cycle counting by Frobenius normal form ⋮ Toward Tight Approximation Bounds for Graph Diameter and Eccentricities ⋮ Algorithms for Weighted Matching Generalizations I: Bipartite Graphs, b-matching, and Unweighted f-factors

This page was built for publication: Algorithmic Applications of Baur-Strassen’s Theorem