时间 | 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.)
| ||