Algebraic Algorithms for b-Matching, Shortest Undirected Paths, and f-Factors

Harold N. Gabow, Piotr Sankowski

Let G=(V,E) be a graph with f:V\to Z_+ a function assigning degree bounds to vertices. We present the first efficient algebraic algorithm to find an f-factor. The time is \tilde{O}…