会员服务
图 ·
2021 年 10 月 10 日
On the complexity of structure and substructure connectivity of graphs
翻译：图表结构和次结构连接的复杂性
Huazhong Lü,Tingzeng Wu
Huazhong Lü,Tingzeng Wu

The connectivity of a graph is an important parameter to measure its reliability. Structure and substructure connectivity are two novel generalizations of the connectivity. In this paper, we characterize the complexity of determining structure and substructure connectivity of graphs, showing that they are both NP-complete.


翻译：图形的连通性是测量其可靠性的一个重要参数。 结构和结构下连接性是连接性的两个新颖的概括。 在本文中,我们描述了确定图形的结构和结构下连接性的复杂性,表明它们都是NP完整的。
0
下载
关闭预览

相关内容

【干货书】开放数据结构，Open Data Structures，337页pdf
【干货书】开放数据结构，Open Data Structures，337页pdf
专知会员服务
18+阅读 · 2021年9月17日
【ICML2020-斯坦福Facebook-何恺明】神经网络图结构，Graph Structure of Neural Networks
【ICML2020-斯坦福Facebook-何恺明】神经网络图结构，Graph Structure of Neural Networks
专知会员服务
57+阅读 · 2020年7月14日
图机器学习-图拉普拉斯算子的离散正则性，141页ppt，Discrete regularity graph Laplacians
专知会员服务
29+阅读 · 2020年6月4日
因果图，Causal Graphs，52页ppt
因果图，Causal Graphs，52页ppt
专知会员服务
253+阅读 · 2020年4月19日
图像分类技巧集，17页ppt《Bag of Tricks for Image Classification》
图像分类技巧集，17页ppt《Bag of Tricks for Image Classification》
专知会员服务
96+阅读 · 2020年3月12日
图机器学习 2.2-2.4 Properties of Networks, Random Graph
图机器学习 2.2-2.4 Properties of Networks, Random Graph
图与推荐
10+阅读 · 2020年3月28日
Hierarchically Structured Meta-learning
Hierarchically Structured Meta-learning
CreateAMind
27+阅读 · 2019年5月22日
Unsupervised Learning via Meta-Learning
Unsupervised Learning via Meta-Learning
CreateAMind
43+阅读 · 2019年1月3日
已删除
已删除
将门创投
7+阅读 · 2018年11月5日
Hierarchical Disentangled Representations
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
EEG-based Emotional Video Classification via Learning Connectivity Structure
Arxiv
0+阅读 · 2021年12月3日
On the Expressivity of Markov Reward
Arxiv
3+阅读 · 2021年11月1日
Self-supervised Graph-level Representation Learning with Local and Global Structure
Arxiv
9+阅读 · 2021年6月8日
Learning Discrete Structures for Graph Neural Networks
Arxiv
17+阅读 · 2019年3月28日
An overview of embedding models of entities and relationships for knowledge base completion
Arxiv
5+阅读 · 2018年2月3日
VIP会员
文章信息
前往arXiv
下载PDF
相关主题
图
相关VIP内容
【干货书】开放数据结构，Open Data Structures，337页pdf
【干货书】开放数据结构，Open Data Structures，337页pdf
专知会员服务
18+阅读 · 2021年9月17日
【ICML2020-斯坦福Facebook-何恺明】神经网络图结构，Graph Structure of Neural Networks
【ICML2020-斯坦福Facebook-何恺明】神经网络图结构，Graph Structure of Neural Networks
专知会员服务
57+阅读 · 2020年7月14日
图机器学习-图拉普拉斯算子的离散正则性，141页ppt，Discrete regularity graph Laplacians
专知会员服务
29+阅读 · 2020年6月4日
因果图，Causal Graphs，52页ppt
因果图，Causal Graphs，52页ppt
专知会员服务
253+阅读 · 2020年4月19日
图像分类技巧集，17页ppt《Bag of Tricks for Image Classification》
图像分类技巧集，17页ppt《Bag of Tricks for Image Classification》
专知会员服务
96+阅读 · 2020年3月12日
热门VIP内容
相关资讯
图机器学习 2.2-2.4 Properties of Networks, Random Graph
图机器学习 2.2-2.4 Properties of Networks, Random Graph
图与推荐
10+阅读 · 2020年3月28日
Hierarchically Structured Meta-learning
Hierarchically Structured Meta-learning
CreateAMind
27+阅读 · 2019年5月22日
Unsupervised Learning via Meta-Learning
Unsupervised Learning via Meta-Learning
CreateAMind
43+阅读 · 2019年1月3日
已删除
已删除
将门创投
7+阅读 · 2018年11月5日
Hierarchical Disentangled Representations
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
相关论文
EEG-based Emotional Video Classification via Learning Connectivity Structure
Arxiv
0+阅读 · 2021年12月3日
On the Expressivity of Markov Reward
Arxiv
3+阅读 · 2021年11月1日
Self-supervised Graph-level Representation Learning with Local and Global Structure
Arxiv
9+阅读 · 2021年6月8日
Learning Discrete Structures for Graph Neural Networks
Arxiv
17+阅读 · 2019年3月28日
An overview of embedding models of entities and relationships for knowledge base completion
Arxiv
5+阅读 · 2018年2月3日
Top
微信扫码咨询专知VIP会员
Top