A bipartite graph B is called a brace if it is connected and every matching of size at most two in B is contained in some perfect matching of B and a cycle C in B is called conformal if B-V(C) has a perfect matching. We show that there do not exist two disjoint alternating paths that form a cross over a conformal cycle C in a brace B if and only if one can reduce B, by an application of a matching theoretic analogue of small clique sums, to a planar brace H in which C bounds a face. We then utilise this result and provide a polynomial time algorithm which solves the 2-linkage problem for alternating paths in bipartite graphs with perfect matchings.


翻译:双部分图B 如果连接在一起,且B中最多两个大小的每个匹配都包含在B和B的一个周期C的完美匹配中,如果B-V(C)有一个完美的匹配,则B和B的周期C就被称为匹配。我们证明,在牙套B中,不存在两个不相连的交替路径,在符合C的周期中形成十字交叉,如果而且只有在能够将B与一个小球形的相匹配的理论类比应用到一个圆形的平板支部H,从而将脸标定在C。我们然后利用这一结果,提供一种多元时间算法,用完美匹配的两部分图解交替路径的2个链接问题。

0
下载
关闭预览

相关内容

【图与几何深度学习】Graph and geometric deep learning,49页ppt
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
【AAAI2020知识图谱论文概述】Knowledge Graphs @ AAAI 2020
专知会员服务
133+阅读 · 2020年2月13日
已删除
将门创投
4+阅读 · 2020年1月6日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
Call for Participation: Shared Tasks in NLPCC 2019
中国计算机学会
5+阅读 · 2019年3月22日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Hierarchical Imitation - Reinforcement Learning
CreateAMind
19+阅读 · 2018年5月25日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Arxiv
0+阅读 · 2021年11月25日
Arxiv
10+阅读 · 2021年11月3日
Arxiv
5+阅读 · 2015年3月1日
VIP会员
相关VIP内容
【图与几何深度学习】Graph and geometric deep learning,49页ppt
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
【AAAI2020知识图谱论文概述】Knowledge Graphs @ AAAI 2020
专知会员服务
133+阅读 · 2020年2月13日
相关资讯
已删除
将门创投
4+阅读 · 2020年1月6日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
Call for Participation: Shared Tasks in NLPCC 2019
中国计算机学会
5+阅读 · 2019年3月22日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Hierarchical Imitation - Reinforcement Learning
CreateAMind
19+阅读 · 2018年5月25日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Top
微信扫码咨询专知VIP会员