![]() |
![]() |
University of Birmingham > Talks@bham > Combinatorics and Probability seminar > Branchings in Digraphs: Structural Results and Algorithms
![]() Branchings in Digraphs: Structural Results and AlgorithmsAdd to your list(s) Download to your calendar using vCal
If you have a question about this talk, please contact Dr Andrew Treglown. 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 zero. 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 algorithmic results obtained for out- and in-branching in directed graphs. We will mainly focus on out-branchings with maximum and minimum number of leaves and on minimizing intersection between an out-branching and in-branching in a digraph. In particular, we will discuss in some detail recent solutions by Felix Reidl, Magnus Wahlstrom and the speaker of two open parameterized problems by Bang-Jensen et al. where one is to decide whether a digraph has an out-branching and in-branching which differ in at least k arcs. This talk is part of the Combinatorics and Probability seminar series. This talk is included in these lists:Note that ex-directory lists are not shown. |
Other listsDinner Table Terrorism - Achieving Food Security Theoretical Physics Seminars SERENE SeminarsOther talksBases for permutation groups The Holographic Universe TBA Integral equation methods for acoustic scattering by fractals Quantifying the economic and environmental effects of the RCEP Kolmogorov-Smirnov type testing for structural breaks: A new adjusted-range based self-normalization approach |