The problem of finding paths in temporal graphs has been recently considered due to its many applications. In this paper we consider a variant of the problem that, given a vertex-colored temporal graph, asks for a path whose vertices have distinct colors and include the maximum number of colors. We study the approximation complexity of the problem and we provide an inapproximability lower bound. Then we present a heuristic for the problem and an experimental evaluation of our heuristic, both on synthetic and real-world graphs.


翻译:最近,由于时间图的多种应用,人们审议了在时间图中寻找路径的问题。在本文中,我们考虑了问题的一个变体,根据一个顶点颜色的时间图,我们要求找到一个顶点有不同颜色的路径,包括最大颜色的路径。我们研究了问题的近似复杂性,我们提供了一个不相容的下限。然后,我们提出了一个问题杂乱无章,并在合成图和现实图上对我们的超常性进行了实验性评估。

0
下载
关闭预览

相关内容

机器学习组合优化
专知会员服务
108+阅读 · 2021年2月16日
数据科学导论,54页ppt,Introduction to Data Science
专知会员服务
41+阅读 · 2020年7月27日
【清华大学】图随机神经网络,Graph Random Neural Networks
专知会员服务
154+阅读 · 2020年5月26日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
MIT-深度学习Deep Learning State of the Art in 2020,87页ppt
专知会员服务
61+阅读 · 2020年2月17日
2019年机器学习框架回顾
专知会员服务
35+阅读 · 2019年10月11日
LibRec 精选:AutoML for Contextual Bandits
LibRec智能推荐
7+阅读 · 2019年9月19日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
已删除
将门创投
3+阅读 · 2018年4月10日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
Arxiv
0+阅读 · 2021年10月25日
On Sparsity Awareness in Distributed Computations
Arxiv
0+阅读 · 2021年10月25日
Arxiv
0+阅读 · 2021年10月25日
Arxiv
0+阅读 · 2021年10月22日
Arxiv
23+阅读 · 2018年10月1日
Arxiv
4+阅读 · 2017年1月2日
VIP会员
相关VIP内容
机器学习组合优化
专知会员服务
108+阅读 · 2021年2月16日
数据科学导论,54页ppt,Introduction to Data Science
专知会员服务
41+阅读 · 2020年7月27日
【清华大学】图随机神经网络,Graph Random Neural Networks
专知会员服务
154+阅读 · 2020年5月26日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
MIT-深度学习Deep Learning State of the Art in 2020,87页ppt
专知会员服务
61+阅读 · 2020年2月17日
2019年机器学习框架回顾
专知会员服务
35+阅读 · 2019年10月11日
相关资讯
LibRec 精选:AutoML for Contextual Bandits
LibRec智能推荐
7+阅读 · 2019年9月19日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
已删除
将门创投
3+阅读 · 2018年4月10日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
相关论文
Arxiv
0+阅读 · 2021年10月25日
On Sparsity Awareness in Distributed Computations
Arxiv
0+阅读 · 2021年10月25日
Arxiv
0+阅读 · 2021年10月25日
Arxiv
0+阅读 · 2021年10月22日
Arxiv
23+阅读 · 2018年10月1日
Arxiv
4+阅读 · 2017年1月2日
Top
微信扫码咨询专知VIP会员