Minimum vertex weighted deficiency of (g,f)-factors: A greedy algorithm
DOI10.1016/0166-218X(93)90235-GzbMATH Open0797.05065OpenAlexW1983091784MaRDI QIDQ686268FDOQ686268
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
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
- Title not available (Why is that?)
- 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 (5)
- Algorithms for Degree Constrained Graph Factors of Minimum Deficiency
- Integer Programming and Combinatorial Optimization
- On the Computational Complexity of Variants of Combinatorial Voter Control in Elections
- Title not available (Why is that?)
- On the approximability of some degree-constrained subgraph problems
Recommendations
- Algorithms for Degree Constrained Graph Factors of Minimum Deficiency 👍 👎
- Title not available (Why is that?) 👍 👎
- 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 👍 👎
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)
