共查询到3条相似文献,搜索用时 0 毫秒
1.
Abdo Y. Alfakih Tongnyoul Yi Katta G. Murty 《Journal of Combinatorial Optimization》2000,4(3):365-388
We show that the problem of finding a perfect matching satisfying a single equality constraint with a 0–1 coefficients in an n × n incomplete bipartite graph, polynomially reduces to a special case of the same peoblem called the partitioned case. Finding a solution matching for the partitioned case in the incomlpete bipartite graph, is equivalent to minimizing a partial sum of the variables over
= the convex hull of incidence vectors of solution matchings for the partitioned case in the complete bipartite graph. An important strategy to solve this minimization problem is to develop a polyhedral characterization of
. Towards this effort, we present two large classes of valid inequalities for
, which are proved to be facet inducing using a facet lifting scheme. 相似文献
2.