Bounds on Maximum Weight Directed Cut

Jiangdong Ai, Stefanie Gerke, Gregory Gutin*, Anders Yeo, Yacong Zhou

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review

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, 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.

Original languageEnglish
JournalSIAM Journal on Discrete Mathematics
Volume38
Issue number3
Pages (from-to)2370-2391
Number of pages22
ISSN0895-4801
DOIs
Publication statusPublished - 2024

Keywords

  • acyclic digraph
  • directed cut
  • weighted digraph

Fingerprint

Dive into the research topics of 'Bounds on Maximum Weight Directed Cut'. Together they form a unique fingerprint.

Cite this