On complexity of special maximum matchings constructing
arXiv:0707.2126 · doi:10.1016/j.disc.2007.04.029
Abstract
For bipartite graphs the NP-completeness is proved for the problem of existence of maximum matching which removal leads to a graph with given lower(upper)bound for the cardinality of its maximum matching.
12 pages, 8 figures. Discrete Mathematics, to appear