Algorithms for Degree Constrained Graph Factors of Minimum Deficiency

DOI10.1006/jagm.1993.1006zbMath0764.68118MaRDI QIDQ4033760

Pavol Hell, David G. 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

complexity; upper bounds; bipartite graphs; NP-hard; perfect matching; efficient algorithm; complexity bounds; \((g,f)\)-factor; maximum flow problem; maximum flow algorithms; minimum deficiency; bipartite matching algorithm; \(g\)-deficiency

Mathematics Subject Classification ID

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.)

Related Items

Unnamed Item, Unnamed Item, Minus domination in small-degree graphs, 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, 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