Bounds on Maximum Weight Directed Cut
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, Bollob\' as, Gy\'arf\'as, Lehel, and Scott [J. Graph Theory, 55 (2007), pp. 1-13] 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.
Authors
- Anders Yeo (ORCID: https://orcid.org/0000-0003-0293-8708)
- Stefanie Gerke (ORCID: https://orcid.org/0000-0002-9426-1708)
- Yacong Zhou (ORCID: https://orcid.org/0000-0002-6988-6968)
- Jiangdong Ai (ORCID: https://orcid.org/0000-0002-5691-3365)
- Gregory Gutin
Institutions
- Royal Holloway University of London (GB)
- Nankai University (CN)
Publication Details
- Journal
- SIAM Journal on Discrete Mathematics
- Published
- 2024-08-29
- DOI
- https://doi.org/10.1137/23m1567394
- Citations
- 1
- Primary Topic
- Optimization and Packing Problems
- Type
- article
- Field-Weighted Citation Impact
- 0.35