报告题目 (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.