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

发布时间:2020-09-21浏览次数:10

 

时间

202092515: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.)

 

 


Baidu
sogou