BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.bham.ac.uk//v3//EN
BEGIN:VEVENT
CATEGORIES:Combinatorics and Probability seminar
SUMMARY:Branchings in Digraphs: Structural Results and Alg
orithms - Gregory Gutin (Royal Holloway)
DTSTART:20170209T150000Z
DTEND:20170209T160000Z
UID:TALK2356AT
URL:/talk/index/2356
DESCRIPTION:An out-tree (in-tree) is an oriented tree in which
only one vertex of in-degree (out-degree) zero. A
leaf in an out-tree is a vertex on out-degree zer
o. An out-branching (in-branching) in a digraph D
is a spanning subgraph of D which is an out-tree (
in-tree). We will overview some structural and alg
orithmic results obtained for out- and in-branchin
g in directed graphs. We will mainly focus on out-
branchings with maximum and minimum number of leav
es and on minimizing intersection between an out-b
ranching and in-branching in a digraph. In particu
lar\, we will discuss in some detail recent soluti
ons by Felix Reidl\, Magnus Wahlstrom and the spea
ker of two open parameterized problems by Bang-Jen
sen et al. where one is to decide whether a digrap
h has an out-branching and in-branching which diff
er in at least k arcs.
LOCATION:LTC Watson
CONTACT:Dr Andrew Treglown
END:VEVENT
END:VCALENDAR