  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}(f(V)^{\omega}). More generally for graphs with
integral edge weights of maximum absolute value W we find a maximum weight
f-factor in time \tilde{O}(Wf(V)^{\omega}). (The algorithms are randomized,
correct with high probability and Las Vegas; the time bound is worst-case.) We
also present three specializations of these algorithms: For maximum weight
perfect f-matching the algorithm is considerably simpler (and almost identical
to its special case of ordinary weighted matching). For the single-source
shortest-path problem in undirected graphs with conservative edge weights, we
present a generalization of the shortest-path tree, and we compute it in
\tilde{O(Wn^{\omega}) time. For bipartite graphs, we improve the known
complexity bounds for vertex capacitated max-flow and min-cost max-flow on a
subclass of graphs.
