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

\((g,f)\)-factor\(g\)-deficiencybipartite graphsbipartite matching algorithmcomplexitycomplexity boundsefficient algorithmmaximum flow algorithmsmaximum flow problemminimum deficiencyNP-hardperfect matchingupper bounds

Mathematics Subject Classification ID

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

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)

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

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)