Motivated by the problem of enumerating all tree decompositions of a graph, we consider in this article the problem of listing all the minimal chordal completions of a graph. In \cite{carmeli2020} (\textsc{Pods 2017}) Carmeli \emph{et al.} proved that all minimal chordal completions or equivalently all proper tree decompositions of a graph can be listed in incremental polynomial time using exponential space. The total running time of their algorithm is quadratic in the number of solutions and the existence of an algorithm whose complexity depends only linearly on the number of solutions remained open. We close this question by providing a polynomial delay algorithm to solve this problem which, moreover, uses polynomial space. Our algorithm relies on \emph{Proximity Search}, a framework recently introduced by Conte \emph{et al.} \cite{conte-uno2019} (\textsc{Stoc 2019}) which has been shown powerful to obtain polynomial delay algorithms, but generally requires exponential space. In order to obtain a polynomial space algorithm for our problem, we introduce a new general method called \emph{canonical path reconstruction} to design polynomial delay and polynomial space algorithms based on proximity search.


翻译:以图的所有树分解问题为动因, 我们在本篇文章中考虑列出图中所有最小的圆形补全的问题。 在\ cite{carmeli2020} (\ textsc{ Pods 2017}) Carmeli \emph{et al.} 证明图中所有最小的圆形补全或等同的所有适当的树分解都可以使用指数空间在递增的多元时段中列出。 它们的算法总运行时间在解决方案的数量上是四级的, 其复杂性仅取决于解决方案数量的线性算法的存在仍然开放。 我们通过提供多元延迟算法来解决这个问题, 并且使用多元空间空间空间空间。 我们的算法依赖于\ emph{ Proximity look}, 由Conte \ emph{et* al.} 引入的框架。\ cite{conti{conti- unooo2019} (\ texticlec{Stoc 2019}) 已经在解决方案中展示了一种强大的算方法, 需要我们获得一个基于空间缩缩缩缩缩缩缩的缩的系统。

0
下载
关闭预览

相关内容

专知会员服务
14+阅读 · 2021年5月21日
【干货书】机器学习速查手册,135页pdf
专知会员服务
125+阅读 · 2020年11月20日
Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
109+阅读 · 2020年5月15日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
151+阅读 · 2019年10月12日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
[综述]深度学习下的场景文本检测与识别
专知会员服务
77+阅读 · 2019年10月10日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
已删除
创业邦杂志
5+阅读 · 2019年3月27日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
强化学习族谱
CreateAMind
26+阅读 · 2017年8月2日
Arxiv
0+阅读 · 2021年9月14日
Arxiv
0+阅读 · 2021年9月13日
Arxiv
0+阅读 · 2021年9月12日
Arxiv
3+阅读 · 2018年10月18日
VIP会员
相关VIP内容
专知会员服务
14+阅读 · 2021年5月21日
【干货书】机器学习速查手册,135页pdf
专知会员服务
125+阅读 · 2020年11月20日
Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
109+阅读 · 2020年5月15日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
151+阅读 · 2019年10月12日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
[综述]深度学习下的场景文本检测与识别
专知会员服务
77+阅读 · 2019年10月10日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
相关资讯
已删除
创业邦杂志
5+阅读 · 2019年3月27日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
强化学习族谱
CreateAMind
26+阅读 · 2017年8月2日
Top
微信扫码咨询专知VIP会员