Recently, Yamazaki et al. provided an algorithm that enumerates all non-isomorphic interval graphs on $n$ vertices with an $O(n^4)$ time delay. In this paper, we improve their algorithm and achieve $O(n^3 \log n)$ time delay. We also extend the catalog of these graphs providing a list of all non-isomorphic interval graphs for all $n$ up to $15$.


翻译:最近,山崎等人提供了一种算法,将所有非单色间距图以美元为单位列出,以美元为单位,延迟时间为美元(n%4),在本文件中,我们改进了它们的算法,并实现了美元(n%3\log n)的延迟时间。我们还扩展了这些图表的目录,提供了所有美元的所有非单色间距图清单,最多不超过1,500美元。

0
下载
关闭预览

相关内容

因果图,Causal Graphs,52页ppt
专知会员服务
238+阅读 · 2020年4月19日
专知会员服务
61+阅读 · 2020年3月4日
17篇知识图谱Knowledge Graphs论文 @AAAI2020
专知会员服务
167+阅读 · 2020年2月13日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
56+阅读 · 2019年10月17日
强化学习最新教程,17页pdf
专知会员服务
167+阅读 · 2019年10月11日
机器学习入门的经验与建议
专知会员服务
90+阅读 · 2019年10月10日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
98+阅读 · 2019年10月9日
17篇必看[知识图谱Knowledge Graphs] 论文@AAAI2020
word2Vec总结
AINLP
3+阅读 · 2019年11月2日
学术报告|UCLA副教授孙怡舟博士
科技创新与创业
9+阅读 · 2019年6月18日
Hierarchically Structured Meta-learning
CreateAMind
23+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
25+阅读 · 2019年5月18日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
【NIPS2018】接收论文列表
专知
5+阅读 · 2018年9月10日
【计算机类】期刊专刊/国际会议截稿信息6条
Call4Papers
3+阅读 · 2017年10月13日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Arxiv
0+阅读 · 2021年4月28日
Arxiv
0+阅读 · 2021年4月27日
Arxiv
7+阅读 · 2018年3月21日
Arxiv
6+阅读 · 2018年2月24日
VIP会员
相关主题
相关VIP内容
因果图,Causal Graphs,52页ppt
专知会员服务
238+阅读 · 2020年4月19日
专知会员服务
61+阅读 · 2020年3月4日
17篇知识图谱Knowledge Graphs论文 @AAAI2020
专知会员服务
167+阅读 · 2020年2月13日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
56+阅读 · 2019年10月17日
强化学习最新教程,17页pdf
专知会员服务
167+阅读 · 2019年10月11日
机器学习入门的经验与建议
专知会员服务
90+阅读 · 2019年10月10日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
98+阅读 · 2019年10月9日
相关资讯
17篇必看[知识图谱Knowledge Graphs] 论文@AAAI2020
word2Vec总结
AINLP
3+阅读 · 2019年11月2日
学术报告|UCLA副教授孙怡舟博士
科技创新与创业
9+阅读 · 2019年6月18日
Hierarchically Structured Meta-learning
CreateAMind
23+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
25+阅读 · 2019年5月18日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
【NIPS2018】接收论文列表
专知
5+阅读 · 2018年9月10日
【计算机类】期刊专刊/国际会议截稿信息6条
Call4Papers
3+阅读 · 2017年10月13日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Top
微信扫码咨询专知VIP会员