Constructive proof of deficiency theorem of (g, f)-factor
发布时间：2025-04-30
点击次数：
- 发布时间：
- 2025-04-30
- 论文名称：
- Constructive proof of deficiency theorem of (g, f)-factor
- 发表刊物：
- Science in China Series A: Mathematics
- 摘要：
- Berge (1958) gave a formula for computing the deficiency of maximum matchings of a graph. More generally, Lovász obtained a deficiency formula of (g, f)-optimal graphs and consequently a criterion for the existence of (g, f)-factors. Moreover, Lovász proved that there is one of these decompositions which is “canonical” in a sense. In this paper, we present a short constructive proof for the deficiency formula of (g, f)-optimal graphs, and the proof implies an efficient algorithm of time complexity O(g(V)|E|) for computing the deficiency. Furthermore, this proof implies this canonical decomposition via efficient algorithms (i.e., in polynomial time).
- 合写作者：
- H. Lu and Q. Yu
- 是否译文：
- 否
- 发表时间：
- 2010-05-08