In this work, we present the first linear time deterministic algorithm computing the 4-edge-connected components of an undirected graph. First, we show an algorithm listing all 3-edge-cuts in a given 3-edge-connected graph, and then we use the output of this algorithm in order to determine the 4-edge-connected components of the graph.


翻译:在这项工作中,我们展示了第一个线性时间确定算法,计算一个无方向图的四端连接元件。首先,我们展示了一种算法,将所有三端切口都列在一个三端连接图中,然后我们用这个算法的输出来确定图表的四端连接元件。

0
下载
关闭预览

相关内容

【干货书】机器学习速查手册,135页pdf
专知会员服务
123+阅读 · 2020年11月20日
一份简单《图神经网络》教程,28页ppt
专知会员服务
120+阅读 · 2020年8月2日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
76+阅读 · 2020年7月26日
Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
107+阅读 · 2020年5月15日
【电子书】大数据挖掘,Mining of Massive Datasets,附513页PDF
专知会员服务
102+阅读 · 2020年3月22日
深度强化学习策略梯度教程,53页ppt
专知会员服务
177+阅读 · 2020年2月1日
【2020新书】图机器学习,Graph-Powered Machine Learning
专知会员服务
338+阅读 · 2020年1月27日
机器学习入门的经验与建议
专知会员服务
91+阅读 · 2019年10月10日
Hierarchically Structured Meta-learning
CreateAMind
23+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
26+阅读 · 2019年5月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
无监督元学习表示学习
CreateAMind
26+阅读 · 2019年1月4日
Unsupervised Learning via Meta-Learning
CreateAMind
41+阅读 · 2019年1月3日
Jointly Improving Summarization and Sentiment Classification
黑龙江大学自然语言处理实验室
3+阅读 · 2018年6月12日
笔记 | Sentiment Analysis
黑龙江大学自然语言处理实验室
10+阅读 · 2018年5月6日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Arxiv
11+阅读 · 2021年2月17日
Arxiv
5+阅读 · 2018年4月22日
VIP会员
相关VIP内容
【干货书】机器学习速查手册,135页pdf
专知会员服务
123+阅读 · 2020年11月20日
一份简单《图神经网络》教程,28页ppt
专知会员服务
120+阅读 · 2020年8月2日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
76+阅读 · 2020年7月26日
Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
107+阅读 · 2020年5月15日
【电子书】大数据挖掘,Mining of Massive Datasets,附513页PDF
专知会员服务
102+阅读 · 2020年3月22日
深度强化学习策略梯度教程,53页ppt
专知会员服务
177+阅读 · 2020年2月1日
【2020新书】图机器学习,Graph-Powered Machine Learning
专知会员服务
338+阅读 · 2020年1月27日
机器学习入门的经验与建议
专知会员服务
91+阅读 · 2019年10月10日
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
23+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
26+阅读 · 2019年5月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
无监督元学习表示学习
CreateAMind
26+阅读 · 2019年1月4日
Unsupervised Learning via Meta-Learning
CreateAMind
41+阅读 · 2019年1月3日
Jointly Improving Summarization and Sentiment Classification
黑龙江大学自然语言处理实验室
3+阅读 · 2018年6月12日
笔记 | Sentiment Analysis
黑龙江大学自然语言处理实验室
10+阅读 · 2018年5月6日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Top
微信扫码咨询专知VIP会员