# 应用数学研究所-学术讲座

 时间 2020年9月25日15:00 至16:30 地点 腾讯会议 ID：111 258 551 主持人 陈旭瑾（中科院数学与系统科学研究院） 联系电话 主题 Weighted Graph Densities and Fractional，Edge-Colorings 拟研讨的主要内容 Given a multigraph G=(V,E) with edge weight $w\in\mathbb Q_(>0)^E$,   the weighted density problem (WDP) is to find a subset U of V with odd size   at least 3 such that the density 2w(U)/(|U|-1) is maximized, where w(U) is   the total weight of all edges with both ends in U. Even for unit weights,   determining whether the WDP can be solved in polynomial time was posed by   Jensen and Toft (2015) and by Stiebitz et al. (2012) as an open problem. The   WDP is closely related to the weighted fractional edge-coloring problem   (WFECP), which is to fractionally decompose G into a minimum amount of   matchings. In this talk, we discuss how to solve the WDP and WFECP exactly in   strongly polynomial time. (Joint work with Wenan Zang and Qiulan Zhao.)