|
|||||
|
|
On complexity of special maximum matchings constructing |
|
| Authors: | R.R. Kamalian V.V. Mkrtchyan |
| Affiliation: | a Institute for Informatics and Automation Problems of National Academy of Sciences of Armenia, 0014, Armenia b Ijevan Branch of Yerevan State University, Armenia c Armenian-Russian State University, Armenia d Department of Informatics and Applied Mathematics, Yerevan State University, 0025, Armenia |
| 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. |
| Keywords: | Maximum matching Bipartite graph NP-completeness |
| 本文献已被 ScienceDirect 等数据库收录！ | |