报告题目:Minimum T-Joins and Signed-Circuit Covering
报 告 人:吴叶舟 浙江大学 教授
报告时间:2021年7月5日10:00-12:00
报告地点:数计学院20幢308
摘要: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.
邀请人:朱绪鼎