We give a dynamic programming solution to find the minimum cost of a diameter constrained Steiner tree in case of directed graphs. Then we show a simple reduction from undirected version to the directed version to realize an algorithm of similar complexity i.e, FPT in number of terminal vertices. Other natural variants of constrained Steiner trees are defined by imposing constraints on the min-degree and size of the Steiner tree and some polynomial time reductions among these problems are proven. To the best of our knowledge, these fairly simple reductions are not present in the literature prior to our work.


翻译:我们给出一个动态的编程解决方案,以找到直径受限的施泰纳树在有定向图表的情况下的最低成本。然后,我们从未定向版本向定向版本简单削减,以实现同样复杂的算法,即终端脊椎数的FPT。 施泰纳树受限的其他自然变体的定义是,对施泰纳树的微度和大小施加限制,以及这些问题中的某些多元时间缩短。 据我们所知,这些相当简单的缩减在我们工作之前的文献中并不存在。

0
下载
关闭预览

相关内容

【开放书】《矩阵流形优化算法》,241页pdf
专知会员服务
93+阅读 · 2021年7月3日
专知会员服务
76+阅读 · 2021年3月16日
专知会员服务
123+阅读 · 2020年9月8日
【Google】平滑对抗训练,Smooth Adversarial Training
专知会员服务
48+阅读 · 2020年7月4日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
最新BERT相关论文清单,BERT-related Papers
专知会员服务
52+阅读 · 2019年9月29日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
CCF A类 | 顶级会议RTSS 2019诚邀稿件
Call4Papers
10+阅读 · 2019年4月17日
学术会议 | 知识图谱顶会 ISWC 征稿:Poster/Demo
开放知识图谱
5+阅读 · 2019年4月16日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
【推荐】决策树/随机森林深入解析
机器学习研究会
5+阅读 · 2017年9月21日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Arxiv
0+阅读 · 2021年12月10日
Arxiv
0+阅读 · 2021年12月10日
Arxiv
3+阅读 · 2018年2月24日
Arxiv
3+阅读 · 2017年12月1日
VIP会员
相关VIP内容
【开放书】《矩阵流形优化算法》,241页pdf
专知会员服务
93+阅读 · 2021年7月3日
专知会员服务
76+阅读 · 2021年3月16日
专知会员服务
123+阅读 · 2020年9月8日
【Google】平滑对抗训练,Smooth Adversarial Training
专知会员服务
48+阅读 · 2020年7月4日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
最新BERT相关论文清单,BERT-related Papers
专知会员服务
52+阅读 · 2019年9月29日
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
CCF A类 | 顶级会议RTSS 2019诚邀稿件
Call4Papers
10+阅读 · 2019年4月17日
学术会议 | 知识图谱顶会 ISWC 征稿:Poster/Demo
开放知识图谱
5+阅读 · 2019年4月16日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
【推荐】决策树/随机森林深入解析
机器学习研究会
5+阅读 · 2017年9月21日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Top
微信扫码咨询专知VIP会员