Bounds on Maximum Weight Directed Cut
From MaRDI portal
Publication:6433729
arXiv2304.10202MaRDI QIDQ6433729FDOQ6433729
Authors: Jiangdong Ai, Stefanie Gerke, G. Gutin, A. Yeo, Y. C. Zhou 
Publication date: 20 April 2023
Abstract: 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.
This page was built for publication: Bounds on Maximum Weight Directed Cut
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6433729)
