当前位置: 首页 / English / Academics / 正文

Good acyclic orientations of unions of spanning trees

作者:   时间:2021-03-11   点击数:

Keynote Speaker:Jørgen Bang-Jensen

Abstract:

Bipolar orientation of G is an acyclic orientation D of G which has a unique source and a unique sink.Our interest is to study graphs which admit a bipolar orientation that contains a pair of arc-disjoint out-branching and in-branching (such an orientation is called good). Thomassen proved that deciding whether a digraph contains a pair of arc-disjoint out-branching and in-branching is an NP-complete problem. A 2T-graph is a graph whose edge set can be decomposed into two edge-disjoint spanning trees. We show connections between the problem of deciding whether a given 2T-graph has a good orientation and matroid theory. We also illustrate to deciding the existence of a good orientation of a 2T-graph can be quite complicated and it is an open problem whether there is a polynomial algorithm for the problem. We also show a number of results on a special class of 2T-graphs, called quartics in which every vertex has degree 3 or 4. Even for this class it is open whether there is a polynomial algorithm. This is joint work with Bessy, Huang, Jackson and Kriesell.

Speaker Introduction:

Jørgen Bang-Jensen, University of Southern Denmark

Inviter:

Yan Jin Professor of School of Mathematics

Time:

20:00 on March 17 (Wednesday); 15:30 on March 18 (Thursday)

Location:

Zoom, ID:546 268 6882, Password:526874

Hosted by: School of Mathematics, Shandong University

地址:中国山东省济南市山大南路27号   邮编:250100  

电话:0531-88364652  院长信箱:sxyuanzhang@sdu.edu.cn

Copyright@ m6体育入口(上海)贸易公司

微信公众号