Bounds on Maximum Weight Directed Cut

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

*Kontaktforfatter

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer 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.

OriginalsprogEngelsk
TidsskriftSIAM Journal on Discrete Mathematics
Vol/bind38
Udgave nummer3
Sider (fra-til)2370-2391
Antal sider22
ISSN0895-4801
DOI
StatusUdgivet - 2024

Fingeraftryk

Dyk ned i forskningsemnerne om 'Bounds on Maximum Weight Directed Cut'. Sammen danner de et unikt fingeraftryk.

Citationsformater