An algorithmic proof of Tutte's f-factor theorem
From MaRDI portal
Publication:5187322
DOI10.1016/0196-6774(85)90022-7zbMath0562.05038OpenAlexW1986600094MaRDI QIDQ5187322
Publication date: 1985
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0196-6774(85)90022-7
Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Related Items
Factors of trees, Construction of k-matchings in graph products, Some Results on Fractional Graph Theory, A polynomial algorithm for b-matchings: An alternative approach, Approximation and Exact Algorithms for Special Cases of Connected f-Factors, Graph factors and factorization: 1985--2003: a survey, Quasi-Eulerian hypergraphs, Rounding in symmetric matrices and undirected graphs, Graph realizations: maximum degree in vertex neighborhoods, Editing graphs to satisfy degree constraints: a parameterized approach, Improved approximation algorithms for the max edge-coloring problem, Finding a \(\Delta\)-regular supergraph of minimum order, Research on fractional critical covered graphs, On the Computational Complexity of Variants of Combinatorial Voter Control in Elections, Efficiently Realizing Interval Sequences, A sufficient condition for the existence of restricted fractional \((g, f)\)-factors in graphs, Matching theory -- a sampler: From Dénes König to the present, Minimum vertex weighted deficiency of \((g,f)\)-factors: A greedy algorithm, Algorithmic complexity of weakly semiregular partitioning and the representation number, Unnamed Item, Orthogonal (g, f)-factorizations in networks, Subgraphs with orthogonal factorizations and algorithms, On fractional \((f,n)\)-critical graphs, Nontrivial path covers of graphs: existence, minimization and maximization, Composed degree-distance realizations of graphs, Composed degree-distance realizations of graphs, Some problems on factorizations with constraints in bipartite graphs, Unnamed Item, Simplified existence theorems for \((g,f)\)-factors, Fractional matching preclusion number of graphs and the perfect matching polytope, A simple existence criterion for \((g<f)\)-factors, Editing to Connected F-Degree Graph, Linear-time certifying algorithms for near-graphical sequences, Unnamed Item, More sufficient conditions for a graph to have factors, 2-factors and Hamiltonicity, \((g, f)\)-factorizations randomly orthogonal to a subgraph in graphs, Forbidden subgraphs for existences of (connected) 2-factors of a graph, Randomly orthogonal \((g,f)\)-factorizations in graphs, Relaxed and approximate graph realizations
