会员服务
图 ·
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
专知会员服务
16+阅读 · 2021年9月17日
AAAI2021 | 图神经网络的异质图结构学习，Heterogeneous Graph Structure Learning for Graph Neural Networks
专知会员服务
91+阅读 · 2021年1月20日
最新《图理论》笔记书，98页pdf
最新《图理论》笔记书，98页pdf
专知会员服务
74+阅读 · 2020年12月27日
【ICML2020-斯坦福Facebook-何恺明】神经网络图结构，Graph Structure of Neural Networks
【ICML2020-斯坦福Facebook-何恺明】神经网络图结构，Graph Structure of Neural Networks
专知会员服务
55+阅读 · 2020年7月14日
最新《3D医疗图像处理》综述论文，23页pdf，3D Deep Learning on Medical Images: A Review
最新《3D医疗图像处理》综述论文，23页pdf，3D Deep Learning on Medical Images: A Review
专知会员服务
58+阅读 · 2020年7月14日
图机器学习-图拉普拉斯算子的离散正则性，141页ppt，Discrete regularity graph Laplacians
专知会员服务
28+阅读 · 2020年6月4日
因果图，Causal Graphs，52页ppt
因果图，Causal Graphs，52页ppt
专知会员服务
246+阅读 · 2020年4月19日
面向结构化数据的向量嵌入理论 | word2vec, node2vec, graph2vec, X2vec: Towards a Theory of Vector Embeddings of Structured Data
面向结构化数据的向量嵌入理论 | word2vec, node2vec, graph2vec, X2vec: Towards a Theory of Vector Embeddings of Structured Data
专知会员服务
50+阅读 · 2020年4月1日
图像分类技巧集，17页ppt《Bag of Tricks for Image Classification》
图像分类技巧集，17页ppt《Bag of Tricks for Image Classification》
专知会员服务
94+阅读 · 2020年3月12日
【MIT】图神经网络的泛化与表示极限，《Generalization and Representational Limits of Graph Neural Networks》
【MIT】图神经网络的泛化与表示极限，《Generalization and Representational Limits of Graph Neural Networks》
专知会员服务
45+阅读 · 2020年2月23日
图机器学习 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
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
无监督元学习表示学习
无监督元学习表示学习
CreateAMind
27+阅读 · 2019年1月4日
Unsupervised Learning via Meta-Learning
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
已删除
已删除
将门创投
7+阅读 · 2018年11月5日
Hierarchical Disentangled Representations
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【学习】Hierarchical Softmax
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Auto-Encoding GAN
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
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日
Structure Aware Negative Sampling in Knowledge Graphs
Arxiv
6+阅读 · 2020年9月23日
GraLSP: Graph Neural Networks with Local Structural Patterns
GraLSP: Graph Neural Networks with Local Structural Patterns
Arxiv
4+阅读 · 2019年11月18日
Structured Query Construction via Knowledge Graph Embedding
Structured Query Construction via Knowledge Graph Embedding
Arxiv
6+阅读 · 2019年9月6日
Learning Discrete Structures for Graph Neural Networks
Arxiv
17+阅读 · 2019年3月28日
Attributed Network Embedding via Subspace Discovery
Arxiv
4+阅读 · 2019年1月14日
Graph Neural Networks: A Review of Methods and Applications
Graph Neural Networks: A Review of Methods and Applications
Arxiv
75+阅读 · 2018年12月20日
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
专知会员服务
16+阅读 · 2021年9月17日
AAAI2021 | 图神经网络的异质图结构学习，Heterogeneous Graph Structure Learning for Graph Neural Networks
专知会员服务
91+阅读 · 2021年1月20日
最新《图理论》笔记书，98页pdf
最新《图理论》笔记书，98页pdf
专知会员服务
74+阅读 · 2020年12月27日
【ICML2020-斯坦福Facebook-何恺明】神经网络图结构，Graph Structure of Neural Networks
【ICML2020-斯坦福Facebook-何恺明】神经网络图结构，Graph Structure of Neural Networks
专知会员服务
55+阅读 · 2020年7月14日
最新《3D医疗图像处理》综述论文，23页pdf，3D Deep Learning on Medical Images: A Review
最新《3D医疗图像处理》综述论文，23页pdf，3D Deep Learning on Medical Images: A Review
专知会员服务
58+阅读 · 2020年7月14日
图机器学习-图拉普拉斯算子的离散正则性，141页ppt，Discrete regularity graph Laplacians
专知会员服务
28+阅读 · 2020年6月4日
因果图，Causal Graphs，52页ppt
因果图，Causal Graphs，52页ppt
专知会员服务
246+阅读 · 2020年4月19日
面向结构化数据的向量嵌入理论 | word2vec, node2vec, graph2vec, X2vec: Towards a Theory of Vector Embeddings of Structured Data
面向结构化数据的向量嵌入理论 | word2vec, node2vec, graph2vec, X2vec: Towards a Theory of Vector Embeddings of Structured Data
专知会员服务
50+阅读 · 2020年4月1日
图像分类技巧集，17页ppt《Bag of Tricks for Image Classification》
图像分类技巧集，17页ppt《Bag of Tricks for Image Classification》
专知会员服务
94+阅读 · 2020年3月12日
【MIT】图神经网络的泛化与表示极限，《Generalization and Representational Limits of Graph Neural Networks》
【MIT】图神经网络的泛化与表示极限，《Generalization and Representational Limits of Graph Neural Networks》
专知会员服务
45+阅读 · 2020年2月23日
热门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
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
无监督元学习表示学习
无监督元学习表示学习
CreateAMind
27+阅读 · 2019年1月4日
Unsupervised Learning via Meta-Learning
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
已删除
已删除
将门创投
7+阅读 · 2018年11月5日
Hierarchical Disentangled Representations
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【学习】Hierarchical Softmax
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Auto-Encoding GAN
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
相关论文
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日
Structure Aware Negative Sampling in Knowledge Graphs
Arxiv
6+阅读 · 2020年9月23日
GraLSP: Graph Neural Networks with Local Structural Patterns
GraLSP: Graph Neural Networks with Local Structural Patterns
Arxiv
4+阅读 · 2019年11月18日
Structured Query Construction via Knowledge Graph Embedding
Structured Query Construction via Knowledge Graph Embedding
Arxiv
6+阅读 · 2019年9月6日
Learning Discrete Structures for Graph Neural Networks
Arxiv
17+阅读 · 2019年3月28日
Attributed Network Embedding via Subspace Discovery
Arxiv
4+阅读 · 2019年1月14日
Graph Neural Networks: A Review of Methods and Applications
Graph Neural Networks: A Review of Methods and Applications
Arxiv
75+阅读 · 2018年12月20日
An overview of embedding models of entities and relationships for knowledge base completion
Arxiv
5+阅读 · 2018年2月3日
Top
微信扫码咨询专知VIP会员
Top