We obtain lower and upper bounds for the maximum weight of a directed cut in the classes of weighted digraphs and weighted acyclic digraphs 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 unweighted 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.
翻译：我们在加权有向图和加权非循环有向图以及它们的一些子类中获得了最大权重有向割的下界和上界。我们将我们的结果与在非加权有向图中获得的最大有向割大小的结果进行比较。特别地，我们表明了阿隆，博洛巴什，吉亚法什，莱赫尔和斯科特 (J Graph Th 55 (1) (2007)) 对于非加权非循环有向图获得的下界可以推广到最大循环长度有界以及每条弧的权重至少为一的加权有向图。我们陈述了一些未解决的问题。
相关内容
微信扫码咨询专知VIP会员