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

DOI10.1016/0166-218X(93)90235-GMaRDI QIDQ686268zbMATH OpenOpenAlexFDO

Authors R. 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

greedy algorithmscost functionsdegree constrained subgraphsfractional factorsfractional subgraphnetwork flow methodsstrongly polynomial algorithms

Mathematics Subject Classification ID

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

Recommendations

• Algorithms for Degree Constrained Graph Factors of Minimum Deficiency
• scientific article; zbMATH DE number 90341
• Connected \((g,f)\)-factors
• More sufficient conditions for a graph to have factors
• Optimization over degree sequences of graphs
• An algorithmic proof of Tutte's f-factor theorem
• Sufficient conditions for graphs to have \((g,f)\)-factors
• Some remarks about factors of graphs
• Constructive proof of deficiency theorem of \((g,f)\)-factor
• Some sufficient conditions for graphs to have (g, f)-factors

Cites work

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

Cited in

(8)

• On the approximability of some degree-constrained subgraph problems
• Constructive proof of deficiency theorem of \((g,f)\)-factor
• Algorithms for Degree Constrained Graph Factors of Minimum Deficiency
• Integer Programming and Combinatorial Optimization
• Minconvex graph factors of prescribed size and a simpler reduction to weighted f-factors
• Linear-time certifying algorithms for near-graphical sequences
• scientific article; zbMATH DE number 90341 (Why is no real title available?)
• On the computational complexity of variants of combinatorial voter control in elections

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q686268)