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
References in corpus (1)
Cited by in corpus (5)
- Characterization Of A Class Of Graphs Related To Pairs Of Disjoint Matchings
- Two polynomial algorithms for special maximum matching constructing in trees
- Three results towards the approximation of special maximum matchings in graphs
- On upper bounds for parameters related to construction of special maximum matchings
- On a constructive characterization of a class of trees related to pairs of disjoint matchings