Algorithms for Degree Constrained Graph Factors of Minimum Deficiency

DOI10.1006/JAGM.1993.1006zbMATH Open0764.68118OpenAlexW2020773010MaRDI QIDQ4033760FDOQ4033760

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

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

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)

Cited In (23)

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

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)