浙江大学 吴叶舟教授 学术报告

时间:2021-07-03浏览:39设置

报告题目:Minimum T-Joins and Signed-Circuit Covering

 

报 告 人:吴叶舟  浙江大学  教授

 

报告时间:20217510:00-12:00

 

报告地点:数计学院20308

 

摘要:Let $G$ be a graph and $T$ be a vertex subset of $G$ with even cardinality. A $T$-join of $G$ is a subset $J$ of edges such that a vertex of $G$ is incident with an odd number of edges in $J$ if and only if the vertex belongs to $T$. Minimum $T$-joins have many applications in combinatorial optimizations. In this paper, we show that a minimum $T$-join of a connected graph $G$ has at most $|E(G)|- 1/2 |E(\widehat{\, G\,})|$ edges where $\widehat{\,G\,}$ is the maximum bidegeless subgraph of $G$.  Further, we are able to use this result to show that every flow-admissible signed graph $(G,\sigma)$ has a signed-circuit cover with length at most $\min(8|E(G)|/3+|V(G)|/2,23|E(G)|/12+3|V(G)|/2)$. Particularly, every flow-admissible signed graph $(G,\sigma)$ with with minimum degree 3 has a signed-circuit cover with length at most $35|E(G)|/12}$. This is joint work with Dong Ye.

 

邀请人:朱绪鼎

 


浙江师范大学离散数学研究中心版权所有 © 2018-2028
地址:浙江省金华市迎宾大道688号21幢 邮政编码:321004
联系电话:0579-82282629   电子邮箱:jcsx@zjnu.cn    管理登陆