正文 | Quick Navigation
通知公告
当前位置: 网站首页 >> 正文

郑州大学王秀梅教授网络学术报告

发布人:    发布时间:2021-11-22    【打印此页】

 

        报告题目:Birkhoff-von Neumann Graphs that are PM-compact

        报  告  人:王秀梅

        工作单位:郑州大学数学与统计学院

        报告时间:2021-11-25  15:00-17:00

        腾讯会议ID:4170675239

        

        报告摘要:

        In any investigation concerning the perfect matching polytope, one may assume that $G$ is matching covered , that is, it is a connected graph (of order at least two) and each edge lies in some perfect matching. A graph $G$ is Birkhoff-von Neumann (BvN) if its perfect matching polytope is characterized solely by non-negativity and degree constraints. A result of Balas (1981) implies that $G$ is BvN if and only if $G$ does not contain a pair of vertex-disjoint odd cycles $(C_1,C_2)$ such that $G-V(C_1)-V(C_2)$ has a perfect matching. It follows immediately that the corresponding decision problem is in co-NP. However, it is not known to be in NP. The problem is in P if the input graph is planar --- due to a result of Carvalho, Lucchesi and Murty (2004). These authors, along with Kothari (2018), have shown that this problem is equivalent to the seemingly unrelated problem of deciding whether a given graph is $\overline{C_6}$-free. 

        报告人简介:

        王秀梅,郑州大学教授,中国运筹学会理事,中国运筹学会图论组合分会理事,中国运筹学会数学优化分会理事,河南省运筹学会常务理事。主要从事图论与组合最优化的研究工作,共发表本研究方向专业学术论文20余篇,其中在数学类top期刊《Mathematical Programming A》发表论文1篇。曾主持2项国家自然科学基金、1项中国博士后科学基金面上资助项目、1项河南省基础与前沿技术研究计划项目, 曾参加的基金项目有7项。获河南省自然科学优秀论文一等奖2项,二等奖3项。获河南省教育厅优秀科技论文一等奖4项。

上一条:南京师范大学王雨顺教授网络学术报告

下一条:同济大学姜立建教授、关晓飞副教授网络学术报告

bat365官网登录入口 中国 河南焦作 高新区 世纪路2001号 [454000]
版权所有 bat365(中国)在线平台官方网站-登录入口