会员服务
图 · SimPLe · 类别 · 论文 · 算法与数据结构 ·
2023 年 3 月 2 日
Treewidth is NP-Complete on Cubic Graphs (and related results)
翻译：树枝是立方图(及相关结果)的NP-完整
Hans L. Bodlaender,Édouard Bonnet,Lars Jaffke,Dušan Knop,Paloma T. Lima,Martin Milanič,Sebastian Ordyniak,Sukanya Pandey,Ondřej Suchý
Hans L. Bodlaender,Édouard Bonnet,Lars Jaffke,Dušan Knop,Paloma T. Lima,Martin Milanič,Sebastian Ordyniak,Sukanya Pandey,Ondřej Suchý

In this paper, we give a very simple proof that Treewidth is NP-complete; this proof also shows NP-completeness on the class of co-bipartite graphs. We then improve the result by Bodlaender and Thilikos from 1997 that Treewidth is NP-complete on graphs with maximum degree at most 9, by showing that Treewidth is NP-complete on cubic graphs.


翻译：在本文中,我们给出了一个非常简单的证据,证明树枝是NP不完整的;这个证据还显示了双边图类中的NP完整性。 然后我们从1997年起改进了Bodlaender和Thilikos的结果,即树枝在图表上是NP完整性的,最大程度最多为9,显示树枝在立方图上是NP完整性的。</s>
0
下载
关闭预览

相关内容

《JADC2 Update—— The What to the How》美国国防信息系统局（DISA）10页slides
《JADC2 Update—— The What to the How》美国国防信息系统局（DISA）10页slides
专知会员服务
41+阅读 · 2022年6月8日
如何使用TensorFlow 排序构建推荐系统? How to build a recommendation system using TensorFlow Ranking?
如何使用TensorFlow 排序构建推荐系统? How to build a recommendation system using TensorFlow Ranking?
专知会员服务
18+阅读 · 2022年3月13日
2020数据工程师成长路线图
专知会员服务
17+阅读 · 2020年9月6日
【新书】数字图像(影像)处理手第二版，2176pdf，Mathematical Methods in Imaging
【新书】数字图像(影像)处理手第二版，2176pdf，Mathematical Methods in Imaging
专知会员服务
86+阅读 · 2020年2月12日
【跨语言BERT模型大集合】Transfer learning is increasingly going multilingual with language-specific BERT models
专知会员服务
52+阅读 · 2020年1月30日
Auto-Sizing the Transformer Network: Improving Speed, Efficiency, and Performance for Low-Resource Machine Translation
Auto-Sizing the Transformer Network: Improving Speed, Efficiency, and Performance for Low-Resource Machine Translation
专知会员服务
45+阅读 · 2019年10月17日
Connections between Support Vector Machines, Wasserstein distance and gradient-penalty GANs
Connections between Support Vector Machines, Wasserstein distance and gradient-penalty GANs
专知会员服务
31+阅读 · 2019年10月17日
Deep Learning Based Detection and Correction of Cardiac MR Motion Artefacts During Reconstruction for High-Quality Segmentation
Deep Learning Based Detection and Correction of Cardiac MR Motion Artefacts During Reconstruction for High-Quality Segmentation
专知会员服务
53+阅读 · 2019年10月17日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
143+阅读 · 2019年10月12日
强化学习最新教程，17页pdf
强化学习最新教程，17页pdf
专知会员服务
167+阅读 · 2019年10月11日
NeurIPS'22上的GNN好文集合 (表示能力、架构设计、图对比/自监督学习、分布偏移、可解释、推荐系统等)
NeurIPS'22上的GNN好文集合 (表示能力、架构设计、图对比/自监督学习、分布偏移、可解释、推荐系统等)
图与推荐
3+阅读 · 2022年9月20日
VCIP 2022 Call for Demos
VCIP 2022 Call for Demos
CCF多媒体专委会
1+阅读 · 2022年6月6日
征稿 | International Joint Conference on Knowledge Graphs (IJCKG)
征稿 | International Joint Conference on Knowledge Graphs (IJCKG)
开放知识图谱
2+阅读 · 2022年5月20日
Multi-Task Learning的几篇综述文章
Multi-Task Learning的几篇综述文章
深度学习自然语言处理
15+阅读 · 2020年6月15日
局部学习的特征选择：Local-Learning-Based Feature Selection
局部学习的特征选择：Local-Learning-Based Feature Selection
我爱读PAMI
14+阅读 · 2019年9月20日
Hierarchically Structured Meta-learning
Hierarchically Structured Meta-learning
CreateAMind
23+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
Transferring Knowledge across Learning Processes
CreateAMind
25+阅读 · 2019年5月18日
Unsupervised Learning via Meta-Learning
Unsupervised Learning via Meta-Learning
CreateAMind
41+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
【推荐】用Tensorflow理解LSTM
【推荐】用Tensorflow理解LSTM
机器学习研究会
36+阅读 · 2017年9月11日
Schr？dinger-Poisson方程守恒DDG方法研究
国家自然科学基金
0+阅读 · 2015年12月31日
长链非编码RNA H19在颞叶癫痫海马神经元凋亡中的作用及调控机制
国家自然科学基金
0+阅读 · 2014年12月31日
Poisson流形上的修正Hamilton方法
国家自然科学基金
0+阅读 · 2014年12月31日
具有临界指数的Schrodinger-Poisson系统的解
国家自然科学基金
0+阅读 · 2013年12月31日
Calderon问题和边界刚性问题
国家自然科学基金
0+阅读 · 2013年12月31日
Beclin 1在阿尔茨海默病样神经元损伤中的调控机制研究
国家自然科学基金
0+阅读 · 2013年12月31日
Fibulin-5/β1-integrin 信号通路在醛固酮诱导血管平滑肌细胞凋亡中的作用
国家自然科学基金
0+阅读 · 2012年12月31日
低熔点金属纳米棒的长径比与熔化特性的关系实验研究
国家自然科学基金
0+阅读 · 2011年12月31日
Walker256肿瘤心梗大鼠同体模型血管新生及赤芍组分干预的分子机制
国家自然科学基金
0+阅读 · 2011年12月31日
柔性微纳米纤维绝热材料的可控制备及传热机理
国家自然科学基金
0+阅读 · 2009年12月31日
Learn to Cluster Faces with Better Subgraphs
Arxiv
0+阅读 · 2023年4月21日
Knowledge Graph Embedding: A Survey from the Perspective of Representation Spaces
Arxiv
18+阅读 · 2022年11月7日
Matrix Decomposition and Applications
Arxiv
54+阅读 · 2022年1月1日
Optimization of Graph Neural Networks: Implicit Acceleration by Skip Connections and More Depth
Arxiv
19+阅读 · 2021年5月10日
MATCH: Metadata-Aware Text Classification in A Large Hierarchy
Arxiv
12+阅读 · 2021年2月15日
Adaptive Universal Generalized PageRank Graph Neural Network
Arxiv
10+阅读 · 2021年1月22日
Temporal Relational Modeling with Self-Supervision for Action Segmentation
Arxiv
13+阅读 · 2020年12月14日
HyperGCN: A New Method of Training Graph Convolutional Networks on Hypergraphs
HyperGCN: A New Method of Training Graph Convolutional Networks on Hypergraphs
Arxiv
13+阅读 · 2019年5月22日
Linkage Based Face Clustering via Graph Convolution Network
Arxiv
16+阅读 · 2019年3月27日
Multi-pseudo Regularized Label for Generated Samples in Person Re-Identification
Arxiv
12+阅读 · 2018年1月29日
VIP会员
文章信息
前往arXiv
下载PDF
相关主题
图
SimPLe
类别
论文
算法与数据结构
相关VIP内容
《JADC2 Update—— The What to the How》美国国防信息系统局（DISA）10页slides
《JADC2 Update—— The What to the How》美国国防信息系统局（DISA）10页slides
专知会员服务
41+阅读 · 2022年6月8日
如何使用TensorFlow 排序构建推荐系统? How to build a recommendation system using TensorFlow Ranking?
如何使用TensorFlow 排序构建推荐系统? How to build a recommendation system using TensorFlow Ranking?
专知会员服务
18+阅读 · 2022年3月13日
2020数据工程师成长路线图
专知会员服务
17+阅读 · 2020年9月6日
【新书】数字图像(影像)处理手第二版，2176pdf，Mathematical Methods in Imaging
【新书】数字图像(影像)处理手第二版，2176pdf，Mathematical Methods in Imaging
专知会员服务
86+阅读 · 2020年2月12日
【跨语言BERT模型大集合】Transfer learning is increasingly going multilingual with language-specific BERT models
专知会员服务
52+阅读 · 2020年1月30日
Auto-Sizing the Transformer Network: Improving Speed, Efficiency, and Performance for Low-Resource Machine Translation
Auto-Sizing the Transformer Network: Improving Speed, Efficiency, and Performance for Low-Resource Machine Translation
专知会员服务
45+阅读 · 2019年10月17日
Connections between Support Vector Machines, Wasserstein distance and gradient-penalty GANs
Connections between Support Vector Machines, Wasserstein distance and gradient-penalty GANs
专知会员服务
31+阅读 · 2019年10月17日
Deep Learning Based Detection and Correction of Cardiac MR Motion Artefacts During Reconstruction for High-Quality Segmentation
Deep Learning Based Detection and Correction of Cardiac MR Motion Artefacts During Reconstruction for High-Quality Segmentation
专知会员服务
53+阅读 · 2019年10月17日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
143+阅读 · 2019年10月12日
强化学习最新教程，17页pdf
强化学习最新教程，17页pdf
专知会员服务
167+阅读 · 2019年10月11日
热门VIP内容
相关资讯
NeurIPS'22上的GNN好文集合 (表示能力、架构设计、图对比/自监督学习、分布偏移、可解释、推荐系统等)
NeurIPS'22上的GNN好文集合 (表示能力、架构设计、图对比/自监督学习、分布偏移、可解释、推荐系统等)
图与推荐
3+阅读 · 2022年9月20日
VCIP 2022 Call for Demos
VCIP 2022 Call for Demos
CCF多媒体专委会
1+阅读 · 2022年6月6日
征稿 | International Joint Conference on Knowledge Graphs (IJCKG)
征稿 | International Joint Conference on Knowledge Graphs (IJCKG)
开放知识图谱
2+阅读 · 2022年5月20日
Multi-Task Learning的几篇综述文章
Multi-Task Learning的几篇综述文章
深度学习自然语言处理
15+阅读 · 2020年6月15日
局部学习的特征选择：Local-Learning-Based Feature Selection
局部学习的特征选择：Local-Learning-Based Feature Selection
我爱读PAMI
14+阅读 · 2019年9月20日
Hierarchically Structured Meta-learning
Hierarchically Structured Meta-learning
CreateAMind
23+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
Transferring Knowledge across Learning Processes
CreateAMind
25+阅读 · 2019年5月18日
Unsupervised Learning via Meta-Learning
Unsupervised Learning via Meta-Learning
CreateAMind
41+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
【推荐】用Tensorflow理解LSTM
【推荐】用Tensorflow理解LSTM
机器学习研究会
36+阅读 · 2017年9月11日
相关论文
Learn to Cluster Faces with Better Subgraphs
Arxiv
0+阅读 · 2023年4月21日
Knowledge Graph Embedding: A Survey from the Perspective of Representation Spaces
Arxiv
18+阅读 · 2022年11月7日
Matrix Decomposition and Applications
Arxiv
54+阅读 · 2022年1月1日
Optimization of Graph Neural Networks: Implicit Acceleration by Skip Connections and More Depth
Arxiv
19+阅读 · 2021年5月10日
MATCH: Metadata-Aware Text Classification in A Large Hierarchy
Arxiv
12+阅读 · 2021年2月15日
Adaptive Universal Generalized PageRank Graph Neural Network
Arxiv
10+阅读 · 2021年1月22日
Temporal Relational Modeling with Self-Supervision for Action Segmentation
Arxiv
13+阅读 · 2020年12月14日
HyperGCN: A New Method of Training Graph Convolutional Networks on Hypergraphs
HyperGCN: A New Method of Training Graph Convolutional Networks on Hypergraphs
Arxiv
13+阅读 · 2019年5月22日
Linkage Based Face Clustering via Graph Convolution Network
Arxiv
16+阅读 · 2019年3月27日
Multi-pseudo Regularized Label for Generated Samples in Person Re-Identification
Arxiv
12+阅读 · 2018年1月29日
相关基金
Schr？dinger-Poisson方程守恒DDG方法研究
国家自然科学基金
0+阅读 · 2015年12月31日
长链非编码RNA H19在颞叶癫痫海马神经元凋亡中的作用及调控机制
国家自然科学基金
0+阅读 · 2014年12月31日
Poisson流形上的修正Hamilton方法
国家自然科学基金
0+阅读 · 2014年12月31日
具有临界指数的Schrodinger-Poisson系统的解
国家自然科学基金
0+阅读 · 2013年12月31日
Calderon问题和边界刚性问题
国家自然科学基金
0+阅读 · 2013年12月31日
Beclin 1在阿尔茨海默病样神经元损伤中的调控机制研究
国家自然科学基金
0+阅读 · 2013年12月31日
Fibulin-5/β1-integrin 信号通路在醛固酮诱导血管平滑肌细胞凋亡中的作用
国家自然科学基金
0+阅读 · 2012年12月31日
低熔点金属纳米棒的长径比与熔化特性的关系实验研究
国家自然科学基金
0+阅读 · 2011年12月31日
Walker256肿瘤心梗大鼠同体模型血管新生及赤芍组分干预的分子机制
国家自然科学基金
0+阅读 · 2011年12月31日
柔性微纳米纤维绝热材料的可控制备及传热机理
国家自然科学基金
0+阅读 · 2009年12月31日
Top
微信扫码咨询专知VIP会员
Top