
arXiv: 2301.11761
Abstract General factors are a generalization of matchings. Given a graph G with a set π(v) of feasible degrees, called a degree constraint, for each vertex v of G, the general factor problem is to find a (spanning) subgraph F of G such that degF(v) ∈ π(v) for every v of G. When all degree constraints are symmetric Δ-matroids, the problem is solvable in polynomial time. The weighted general factor problem is to find a general factor of the maximum total weight in an edge-weighted graph. In this paper, we present a strongly polynomial-time algorithm for a type of weighted general factor problems with real-valued edge weights that is provably not reducible to the weighted matching problem by gadget constructions.
FOS: Computer and information sciences, Discrete Mathematics (cs.DM), factors, delta matroids, terminal backup problem, Computational Complexity (cs.CC), 004, edge constraint satisfaction problems, Computer Science - Computational Complexity, Computer Science - Data Structures and Algorithms, Data Structures and Algorithms (cs.DS), matchings, Computer Science - Discrete Mathematics, ddc: ddc:004
FOS: Computer and information sciences, Discrete Mathematics (cs.DM), factors, delta matroids, terminal backup problem, Computational Complexity (cs.CC), 004, edge constraint satisfaction problems, Computer Science - Computational Complexity, Computer Science - Data Structures and Algorithms, Data Structures and Algorithms (cs.DS), matchings, Computer Science - Discrete Mathematics, ddc: ddc:004
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
