报告题目 (Title)：最大权重有向割的边界 (Bounds on Maximum Weight Directed Cut)

报告人 (Speaker)：艾江东 教授（南开大学）

报告时间 (Time)：2023年07月04日(周二) 11:00

报告地点 (Place)：校本部F309

邀请人(Inviter)：袁西英 教授

主办部门：理学院数学系

报告摘要：We obtain lower and upper bounds for the maximum weight of a directed cut in the classes of weighted digraphs and weighted acyclic di- graphs as well as in some of their subclasses. We compare our results with those obtained for the maximum size of a directed cut in unweighted digraphs. In particular, we show that a lower bound obtained by Alon, Bollobas, Gyafas, Lehel and Scott (J Graph Th 55(1) (2007)) for un- weighted acyclic digraphs can be extended to weighted digraphs with the maximum length of a cycle being bounded by a constant and the weight of every arc being at least one. We state a number of open problems.