×

An algorithmic proof of Tutte’s f-factor theorem. (English) Zbl 0562.05038

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

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
68R10 Graph theory (including graph drawing) in computer science
PDFBibTeX XMLCite
Full Text: DOI