Minimum vertex weighted deficiency of \((g,f)\)-factors: A greedy algorithm

DOI10.1016/0166-218X(93)90235-GzbMath0797.05065OpenAlexW1983091784MaRDI QIDQ686268

Richard P. Anstee

Publication date: 30 November 1993

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(93)90235-g

zbMATH Keywords

cost functionsgreedy algorithmsdegree constrained subgraphsfractional factorsfractional subgraphnetwork flow methodsstrongly polynomial algorithms

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Deterministic network models in operations research (90B10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (2)

On the approximability of some degree-constrained subgraph problems ⋮ On the Computational Complexity of Variants of Combinatorial Voter Control in Elections

Cites Work

• Unnamed Item
• A strongly polynomial minimum cost circulation algorithm
• Matching theory
• Simplified existence theorems for \((g,f)\)-factors
• Algorithms for Degree Constrained Graph Factors of Minimum Deficiency
• An algorithmic proof of Tutte's f-factor theorem
• Paths, Trees, and Flowers
• Some Properties of Graphs with Multiple Edges
• Subgraphs with prescribed valencies
• A Short Proof of the Factor Theorem for Finite Graphs

This page was built for publication: Minimum vertex weighted deficiency of \((g,f)\)-factors: A greedy algorithm