管理员登录 / English
Densities, Matchings, and Fractional Edge-Colorings
发布时间: 2018-10-09     20:07   【返回上一页】 发布人:陈旭瑾


北京师范大学数学科学学院

 

图论与组合优化学术报告

 

 

报告题目:Densities, Matchings, and Fractional Edge-Colorings

 

报告人:陈旭瑾研究员(中国科学院数学与系统科学研究院)

 

时间地点: 2018年10月25日15:40-16:40,后主楼1124

 

邀请人:徐敏

 

报告摘要: Given a multigraph G=(V,E) with a positive rational weight w(e) on each edge e, the weighted density problem is to find a subset Uof V, with u>=3 and odd, that maximizes 2w(u)/|u|-1, where w(U) is the total weight of all edges with both ends in U, and the weighted fractional edge-coloring problemcan be formulated as the linear program

Minimize   1^Tu

subject to   Axw  

x>=0   

where Ais the edge-matching incidence matrix of G. These two problems are closely related to the celebrated Goldberg-Seymour conjecture on edge-colorings of multigraphs, and have great interests in their own rights. We design strongly polynomial-time algorithms for solving them exactly, and develop a novel matching removal technique for multigraph edge-coloring. (Joint work with Wenan Zang, Qiulan Zhao.)