Minimum vertex weighted deficiency of (g,f)-factors: A greedy algorithm
DOI10.1016/0166-218X(93)90235-GzbMATH Open0797.05065OpenAlexW1983091784MaRDI QIDQ686268FDOQ686268
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
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
greedy algorithmscost functionsdegree constrained subgraphsfractional factorsfractional subgraphnetwork flow methodsstrongly polynomial algorithms
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)
Cites Work
- Graph theory
- Matching theory
- Paths, Trees, and Flowers
- Some Properties of Graphs with Multiple Edges
- A strongly polynomial minimum cost circulation algorithm
- A Short Proof of the Factor Theorem for Finite Graphs
- Subgraphs with prescribed valencies
- An algorithmic proof of Tutte's f-factor theorem
- Algorithms for Degree Constrained Graph Factors of Minimum Deficiency
- Simplified existence theorems for \((g,f)\)-factors
Cited In (8)
- Minconvex graph factors of prescribed size and a simpler reduction to weighted f-factors
- Linear-time certifying algorithms for near-graphical sequences
- Algorithms for Degree Constrained Graph Factors of Minimum Deficiency
- On the computational complexity of variants of combinatorial voter control in elections
- Constructive proof of deficiency theorem of \((g,f)\)-factor
- Integer Programming and Combinatorial Optimization
- Title not available (Why is that?)
- On the approximability of some degree-constrained subgraph problems
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)
