Anstee, R. P. An algorithmic proof of Tutte’s f-factor theorem. (English) Zbl 0562.05038 J. Algorithms 6, 112-131 (1985). Multigraphs are considered, loops are admitted. The vertices of a multigraph G are numbered by the numbers 1,...,n. An f-factor is a subgraph of G in which the vertex i has the prescribed degree \(f_ i\) for \(i=1,...,n\). A (g,f)-factor is a subgraph of G in which the vertex i has the degree \(d_ i\) for which \(g_ i\leq d_ i\leq f_ i\) holds with prescribed numbers \(g_ i\), \(f_ i\) for \(i=1,..,n\). An existence theorem for f-factors was proved by W. T. Tutte, for (g,f)-factors by L. Lovász. In this paper algorithms are described which either find an f- factor (or a (g,f)-factor, respectively), or show that it does not exist. Both the algorithms require \(O(n^ 3)\) operations. Reviewer: B.Zelinka Cited in 2 ReviewsCited in 40 Documents MSC: 05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) 68R10 Graph theory (including graph drawing) in computer science Keywords:f-factor; (g,f)-factor; algorithms PDFBibTeX XMLCite \textit{R. P. Anstee}, J. Algorithms 6, 112--131 (1985; Zbl 0562.05038) Full Text: DOI