Algorithms for Degree Constrained Graph Factors of Minimum Deficiency

DOI10.1006/JAGM.1993.1006MaRDI QIDQ4033760zbMATH OpenOpenAlexFDO

Authors Pavol Hell, David Kirkpatrick

Publication date 16 May 1993

Published in Journal of Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/jagm.1993.1006

zbMATH Keywords

complexityNP-hardperfect matchingbipartite graphsefficient algorithmupper boundsmaximum flow problemcomplexity boundsmaximum flow algorithms\((g,f)\)-factorminimum deficiencybipartite matching algorithm\(g\)-deficiency

Mathematics Subject Classification ID

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

• Minimum vertex weighted deficiency of (g,f)-factors: A greedy algorithm
• Some problems on factorizations with constraints in bipartite graphs
• Constructive proof of deficiency theorem of \((g,f)\)-factor
• An algorithmic proof of Tutte's f-factor theorem
• scientific article; zbMATH DE number 90341

Cited in

(24)

• \((g, f)\)-factorizations randomly orthogonal to a subgraph in graphs
• Constructive proof of deficiency theorem of \((g,f)\)-factor
• Minimum vertex weighted deficiency of \((g,f)\)-factors: A greedy algorithm
• A simple existence criterion for \((g<f)\)-factors
• Subgraphs with orthogonal factorizations and algorithms
• Simplified existence theorems for \((g,f)\)-factors
• How many matchings cover the nodes of a graph?
• Minus domination in small-degree graphs
• Randomly orthogonal \((g,f)\)-factorizations in graphs
• Decompositions to degree-constrained subgraphs are simply reducible to edge-colorings
• Rounding in symmetric matrices and undirected graphs
• Correlation clustering with constrained cluster sizes and extended weights bounds
• Integer Programming and Combinatorial Optimization
• A Short Proof of Ore’s f-Factor Theorem Using Flows
• Orthogonal (g, f)-factorizations in networks
• scientific article; zbMATH DE number 1769330 (Why is no real title available?)
• Minconvex graph factors of prescribed size and a simpler reduction to weighted f-factors
• Greedily constructing maximal partial \(f\)-factors
• Linear-time certifying algorithms for near-graphical sequences
• Some problems on factorizations with constraints in bipartite graphs
• scientific article; zbMATH DE number 90341 (Why is no real title available?)
• Dulmage-Mendelsohn canonical decomposition as a generic pruning technique
• An algorithmic proof of Tutte's f-factor theorem
• Minconvex Factors of Prescribed Size in Graphs

This page was built for publication: Algorithms for Degree Constrained Graph Factors of Minimum Deficiency

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