A strongly polynomial-time algorithm for weighted general factors with three feasible degrees
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 s...
Main Authors: | Shao, S, Zivny, S |
---|---|
Format: | Conference item |
Language: | English |
Published: |
Schloss-Dagstuhl - Leibniz Zentrum für Informatik
2023
|
Similar Items
-
Polynomial time algorithm for checking strong equivalence of program
by: V. A. Zakharov, et al.
Published: (2018-10-01) -
Polynomial time algorithm for checking strong equivalence of program
by: T. A. Novikova, et al.
Published: (2018-10-01) -
Impact of decreasing polynomial degree in time needed to factor a 100 digits integer by General Number field sieve algorithm
by: Jamal A. Othman
Published: (2012-02-01) -
Weighted inequalities for generalized polynomials with doubling weights
by: Haewon Joung
Published: (2017-04-01) -
A faster strongly polynomial minimum cost flow algorithm
Published: (2004)