会员服务
图 · SimPLe · 类别 · 论文 · 算法与数据结构 ·
2023 年 1 月 24 日
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完整性的。
0
下载
关闭预览

相关内容

不可错过！《机器学习100讲》课程，UBC Mark Schmidt讲授
不可错过！《机器学习100讲》课程，UBC Mark Schmidt讲授
专知会员服务
73+阅读 · 2022年6月28日
高效可扩展图神经网络的研究进展，Recent Advances in Efficient and Scalable Graph Neural Networks
高效可扩展图神经网络的研究进展，Recent Advances in Efficient and Scalable Graph Neural Networks
专知会员服务
75+阅读 · 2022年3月15日
深度学习优化算法，73页ppt，Optimization Algorithms on Deep Learning
深度学习优化算法，73页ppt，Optimization Algorithms on Deep Learning
专知会员服务
132+阅读 · 2021年6月16日
图像分类技巧集，17页ppt《Bag of Tricks for Image Classification》
图像分类技巧集，17页ppt《Bag of Tricks for Image Classification》
专知会员服务
94+阅读 · 2020年3月12日
【新书】数字图像(影像)处理手第二版，2176pdf，Mathematical Methods in Imaging
【新书】数字图像(影像)处理手第二版，2176pdf，Mathematical Methods in Imaging
专知会员服务
88+阅读 · 2020年2月12日
Aspect-Oriented Syntax Network for Aspect-Based Sentiment Analysis，中山大学数据科学与计算机学院权小军教授，第八届全国社会媒体处理大会SMP2019
Aspect-Oriented Syntax Network for Aspect-Based Sentiment Analysis，中山大学数据科学与计算机学院权小军教授，第八届全国社会媒体处理大会SMP2019
专知会员服务
18+阅读 · 2019年10月22日
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
专知会员服务
47+阅读 · 2019年10月17日
强化学习最新教程，17页pdf
强化学习最新教程，17页pdf
专知会员服务
174+阅读 · 2019年10月11日
机器学习入门的经验与建议
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
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日
VCIP 2022 Call for Special Session Proposals
VCIP 2022 Call for Special Session Proposals
CCF多媒体专委会
1+阅读 · 2022年4月1日
IEEE ICKG 2022: Call for Papers
IEEE ICKG 2022: Call for Papers
机器学习与推荐算法
3+阅读 · 2022年3月30日
AIART 2022 Call for Papers
AIART 2022 Call for Papers
CCF多媒体专委会
1+阅读 · 2022年2月13日
局部学习的特征选择：Local-Learning-Based Feature Selection
局部学习的特征选择：Local-Learning-Based Feature Selection
我爱读PAMI
14+阅读 · 2019年9月20日
Hierarchically Structured Meta-learning
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
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日
Capsule Networks解析
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
【推荐】深度学习目标检测概览
【推荐】深度学习目标检测概览
机器学习研究会
10+阅读 · 2017年9月1日
非线性Schrödinger方程孤立子和怪波的数值方法
国家自然科学基金
0+阅读 · 2015年12月31日
Cx43半通道介导PGE2释放在异常咬合所致髁突软骨退变中的作用
国家自然科学基金
0+阅读 · 2015年12月31日
基于数值模拟方法的大曲率弯道演变机理研究
国家自然科学基金
0+阅读 · 2015年12月31日
社区分异演变视域下的社区公共空间规划研究
国家自然科学基金
0+阅读 · 2013年12月31日
Kronheimer-Nakajima quiver 模空间与有理曲面
国家自然科学基金
1+阅读 · 2013年12月31日
Arisandilactone A 的不对称全合成
国家自然科学基金
0+阅读 · 2012年12月31日
纳米结构中热输运机理研究
国家自然科学基金
0+阅读 · 2011年12月31日
相关于算子的Orlicz-型函数空间的实变理论
国家自然科学基金
0+阅读 · 2011年12月31日
脑肠肽ghrelin与帕金森病早期发生发展的关系研究
国家自然科学基金
0+阅读 · 2011年12月31日
W、Re对单晶高温合金再结晶形核与长大的影响
国家自然科学基金
0+阅读 · 2009年12月31日
Hardness of the Generalized Coloring Numbers
Arxiv
0+阅读 · 2023年3月16日
On the Robustness of Normalizing Flows for Inverse Problems in Imaging
Arxiv
0+阅读 · 2023年3月16日
Stable Set Polytopes with High Lift-and-Project Ranks for the Lovász-Schrijver SDP Operator
Arxiv
0+阅读 · 2023年3月15日
The Number of Edges in Maximal 2-planar Graphs
Arxiv
0+阅读 · 2023年3月15日
Gaussian Heteroskedastic Empirical Bayes without Independence
Arxiv
0+阅读 · 2023年3月15日
On the width of complicated JSJ decompositions
Arxiv
0+阅读 · 2023年3月14日
Logarithmic Weisfeiler--Leman and Treewidth
Arxiv
0+阅读 · 2023年3月14日
Automated Ensemble Search Framework for Semantic Segmentation Using Medical Imaging Labels
Arxiv
0+阅读 · 2023年3月14日
Drawings of Complete Multipartite Graphs Up to Triangle Flips
Arxiv
0+阅读 · 2023年3月13日
Zero-shot Recognition via Semantic Embeddings and Knowledge Graphs
Arxiv
18+阅读 · 2018年4月8日
VIP会员
文章信息
前往arXiv
下载PDF
相关主题
图
SimPLe
类别
论文
算法与数据结构
相关VIP内容
不可错过！《机器学习100讲》课程，UBC Mark Schmidt讲授
不可错过！《机器学习100讲》课程，UBC Mark Schmidt讲授
专知会员服务
73+阅读 · 2022年6月28日
高效可扩展图神经网络的研究进展，Recent Advances in Efficient and Scalable Graph Neural Networks
高效可扩展图神经网络的研究进展，Recent Advances in Efficient and Scalable Graph Neural Networks
专知会员服务
75+阅读 · 2022年3月15日
深度学习优化算法，73页ppt，Optimization Algorithms on Deep Learning
深度学习优化算法，73页ppt，Optimization Algorithms on Deep Learning
专知会员服务
132+阅读 · 2021年6月16日
图像分类技巧集，17页ppt《Bag of Tricks for Image Classification》
图像分类技巧集，17页ppt《Bag of Tricks for Image Classification》
专知会员服务
94+阅读 · 2020年3月12日
【新书】数字图像(影像)处理手第二版，2176pdf，Mathematical Methods in Imaging
【新书】数字图像(影像)处理手第二版，2176pdf，Mathematical Methods in Imaging
专知会员服务
88+阅读 · 2020年2月12日
Aspect-Oriented Syntax Network for Aspect-Based Sentiment Analysis，中山大学数据科学与计算机学院权小军教授，第八届全国社会媒体处理大会SMP2019
Aspect-Oriented Syntax Network for Aspect-Based Sentiment Analysis，中山大学数据科学与计算机学院权小军教授，第八届全国社会媒体处理大会SMP2019
专知会员服务
18+阅读 · 2019年10月22日
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
专知会员服务
47+阅读 · 2019年10月17日
强化学习最新教程，17页pdf
强化学习最新教程，17页pdf
专知会员服务
174+阅读 · 2019年10月11日
机器学习入门的经验与建议
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
热门VIP内容
相关资讯
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日
VCIP 2022 Call for Special Session Proposals
VCIP 2022 Call for Special Session Proposals
CCF多媒体专委会
1+阅读 · 2022年4月1日
IEEE ICKG 2022: Call for Papers
IEEE ICKG 2022: Call for Papers
机器学习与推荐算法
3+阅读 · 2022年3月30日
AIART 2022 Call for Papers
AIART 2022 Call for Papers
CCF多媒体专委会
1+阅读 · 2022年2月13日
局部学习的特征选择：Local-Learning-Based Feature Selection
局部学习的特征选择：Local-Learning-Based Feature Selection
我爱读PAMI
14+阅读 · 2019年9月20日
Hierarchically Structured Meta-learning
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
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日
Capsule Networks解析
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
【推荐】深度学习目标检测概览
【推荐】深度学习目标检测概览
机器学习研究会
10+阅读 · 2017年9月1日
相关论文
Hardness of the Generalized Coloring Numbers
Arxiv
0+阅读 · 2023年3月16日
On the Robustness of Normalizing Flows for Inverse Problems in Imaging
Arxiv
0+阅读 · 2023年3月16日
Stable Set Polytopes with High Lift-and-Project Ranks for the Lovász-Schrijver SDP Operator
Arxiv
0+阅读 · 2023年3月15日
The Number of Edges in Maximal 2-planar Graphs
Arxiv
0+阅读 · 2023年3月15日
Gaussian Heteroskedastic Empirical Bayes without Independence
Arxiv
0+阅读 · 2023年3月15日
On the width of complicated JSJ decompositions
Arxiv
0+阅读 · 2023年3月14日
Logarithmic Weisfeiler--Leman and Treewidth
Arxiv
0+阅读 · 2023年3月14日
Automated Ensemble Search Framework for Semantic Segmentation Using Medical Imaging Labels
Arxiv
0+阅读 · 2023年3月14日
Drawings of Complete Multipartite Graphs Up to Triangle Flips
Arxiv
0+阅读 · 2023年3月13日
Zero-shot Recognition via Semantic Embeddings and Knowledge Graphs
Arxiv
18+阅读 · 2018年4月8日
相关基金
非线性Schrödinger方程孤立子和怪波的数值方法
国家自然科学基金
0+阅读 · 2015年12月31日
Cx43半通道介导PGE2释放在异常咬合所致髁突软骨退变中的作用
国家自然科学基金
0+阅读 · 2015年12月31日
基于数值模拟方法的大曲率弯道演变机理研究
国家自然科学基金
0+阅读 · 2015年12月31日
社区分异演变视域下的社区公共空间规划研究
国家自然科学基金
0+阅读 · 2013年12月31日
Kronheimer-Nakajima quiver 模空间与有理曲面
国家自然科学基金
1+阅读 · 2013年12月31日
Arisandilactone A 的不对称全合成
国家自然科学基金
0+阅读 · 2012年12月31日
纳米结构中热输运机理研究
国家自然科学基金
0+阅读 · 2011年12月31日
相关于算子的Orlicz-型函数空间的实变理论
国家自然科学基金
0+阅读 · 2011年12月31日
脑肠肽ghrelin与帕金森病早期发生发展的关系研究
国家自然科学基金
0+阅读 · 2011年12月31日
W、Re对单晶高温合金再结晶形核与长大的影响
国家自然科学基金
0+阅读 · 2009年12月31日
Top
微信扫码咨询专知VIP会员
Top