Minimum vertex weighted deficiency of \((g,f)\)-factors: A greedy algorithm
From MaRDI portal
Publication:686268
DOI10.1016/0166-218X(93)90235-GzbMath0797.05065MaRDI QIDQ686268
Publication date: 30 November 1993
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
cost functions; greedy algorithms; degree constrained subgraphs; fractional factors; fractional subgraph; network flow methods; strongly polynomial algorithms
05C35: Extremal problems in graph theory
68R10: Graph theory (including graph drawing) in computer science
90B10: Deterministic network models in operations research
05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C85: Graph algorithms (graph-theoretic aspects)
Related Items
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