»ã±¨±êÌâ (Title)£º×î´óȨ³ÁÓÐÏò¸îµÄÌìǵ (Bounds on Maximum Weight Directed Cut)

»ã±¨ÈË (Speaker)£º°¬½­¶« ½ÌÊÚ£¨ÄÏ¿ª´óѧ£©

»ã±¨¹¦·ò (Time)£º2023Äê07ÔÂ04ÈÕ(Öܶþ) 11:00

»ã±¨µØÖ· (Place)£ºÐ£±¾²¿F309

Ô¼ÇëÈË(Inviter)£ºÔ¬Î÷Ó¢ ½ÌÊÚ

Ö÷°ì²¿ÃÅ£ºÀíѧԺÊýѧϵ

»ã±¨ÌáÒª£ºWe obtain lower and upper bounds for the maximum weight of a directed cut in the classes of weighted digraphs and weighted acyclic di- graphs 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 un- weighted 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.