会员服务
极小点 · FPT · 路径 · 图 · 无向图 ·
2021 年 6 月 27 日
Minimum Eccentricity Shortest Path Problem with Respect to Structural Parameters
翻译：结构性参数方面最短路径问题
Martin Kučera,Ondřej Suchý
Martin Kučera,Ondřej Suchý

The Minimum Eccentricity Shortest Path Problem consists in finding a shortest path with minimum eccentricity in a given undirected graph. The problem is known to be NP-complete and W[2]-hard with respect to the desired eccentricity. We present fpt algorithms for the problem parameterized by the modular width, distance to cluster graph, the combination of distance to disjoint paths with the desired eccentricity, and maximum leaf number.


翻译：最小偏心最短路径问题在于在给定的无方向图中找到一条最短路径,其中最小偏心。 在理想偏心方面,这个问题已知为NP-完整和W[2]-硬。 我们为按模块宽度、离群集图的距离、距离至偏心偏心路径断开的路径的结合以及最大叶数测定的问题提供了假算法。
0
下载
关闭预览

相关内容

【KDD2021】图神经网络，NUS- Xavier Bresson教授
【KDD2021】图神经网络，NUS- Xavier Bresson教授
专知会员服务
62+阅读 · 2021年8月20日
INRIA 最新《机器学习理论》课程笔记，176页pdf
专知会员服务
50+阅读 · 2020年12月14日
Linux导论，Introduction to Linux，96页ppt
Linux导论，Introduction to Linux，96页ppt
专知会员服务
77+阅读 · 2020年7月26日
Fariz Darari简明《博弈论Game Theory》介绍，35页ppt
Fariz Darari简明《博弈论Game Theory》介绍，35页ppt
专知会员服务
109+阅读 · 2020年5月15日
因果图，Causal Graphs，52页ppt
因果图，Causal Graphs，52页ppt
专知会员服务
246+阅读 · 2020年4月19日
【NeurlPS2019论文总结】一致收敛可能无法解释深度学习中的泛化现象，Uniform convergence may be unable to explain generalization in deep learning
【NeurlPS2019论文总结】一致收敛可能无法解释深度学习中的泛化现象，Uniform convergence may be unable to explain generalization in deep learning
专知会员服务
14+阅读 · 2019年12月17日
【北京智源大会2019】 神经网络的优化Optimization for Overparametrized Deep Neural Networks，北京大学 | 王立威
【北京智源大会2019】 神经网络的优化Optimization for Overparametrized Deep Neural Networks，北京大学 | 王立威
专知会员服务
22+阅读 · 2019年11月21日
【ICCV 2019 Toturial】Global Optimization for Geometric Understanding with Provable Guarantees（具有可证明保证的几何理解的全局优化）
【ICCV 2019 Toturial】Global Optimization for Geometric Understanding with Provable Guarantees（具有可证明保证的几何理解的全局优化）
专知会员服务
15+阅读 · 2019年11月1日
【ICCV 2019 Workshop】Complete Dictionary Learning via L4-Norm Maximization over the Orthogonal Grou， 加州大学伯克利分校 马毅
【ICCV 2019 Workshop】Complete Dictionary Learning via L4-Norm Maximization over the Orthogonal Grou， 加州大学伯克利分校 马毅
专知会员服务
15+阅读 · 2019年10月31日
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日
Hierarchically Structured Meta-learning
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
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日
Disentangled的假设的探讨
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
已删除
已删除
将门创投
4+阅读 · 2018年6月26日
【关关的刷题日记63】Leetcode 111 Minimum Depth of Binary Tree
【关关的刷题日记63】Leetcode 111 Minimum Depth of Binary Tree
专知
6+阅读 · 2017年12月11日
关关的刷题日记13——Leetcode 414. Third Maximum Number
关关的刷题日记13——Leetcode 414. Third Maximum Number
专知
3+阅读 · 2017年10月8日
【学习】Hierarchical Softmax
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
强化学习 cartpole_a3c
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Poising on Ariadne's thread: An algorithm for computing a maximum clique in polynomial time
Arxiv
0+阅读 · 2021年8月30日
Quantum Cross Entropy and Maximum Likelihood Principle
Quantum Cross Entropy and Maximum Likelihood Principle
Arxiv
0+阅读 · 2021年8月26日
Approximation algorithms for the random-field Ising model
Arxiv
0+阅读 · 2021年8月26日
Quasi-upward Planar Drawings with Minimum Curve Complexity
Quasi-upward Planar Drawings with Minimum Curve Complexity
Arxiv
0+阅读 · 2021年8月26日
Adaptively detect and accurately resolve macro-scale shocks in an efficient Equation-Free multiscale simulation
Arxiv
0+阅读 · 2021年8月26日
Dynamic Structural Clustering on Graphs
Arxiv
0+阅读 · 2021年8月26日
Minimum-Distortion Embedding
Arxiv
0+阅读 · 2021年8月24日
Minimal Variance Sampling with Provable Guarantees for Fast Training of Graph Neural Networks
Minimal Variance Sampling with Provable Guarantees for Fast Training of Graph Neural Networks
Arxiv
13+阅读 · 2020年6月24日
Implicit Maximum Likelihood Estimation
Implicit Maximum Likelihood Estimation
Arxiv
7+阅读 · 2018年9月24日
A fast algorithm with minimax optimal guarantees for topic models with an unknown number of topics
Arxiv
7+阅读 · 2018年6月12日
VIP会员
文章信息
前往arXiv
下载PDF
相关主题
极小点
FPT
路径
图
无向图
相关VIP内容
【KDD2021】图神经网络，NUS- Xavier Bresson教授
【KDD2021】图神经网络，NUS- Xavier Bresson教授
专知会员服务
62+阅读 · 2021年8月20日
INRIA 最新《机器学习理论》课程笔记，176页pdf
专知会员服务
50+阅读 · 2020年12月14日
Linux导论，Introduction to Linux，96页ppt
Linux导论，Introduction to Linux，96页ppt
专知会员服务
77+阅读 · 2020年7月26日
Fariz Darari简明《博弈论Game Theory》介绍，35页ppt
Fariz Darari简明《博弈论Game Theory》介绍，35页ppt
专知会员服务
109+阅读 · 2020年5月15日
因果图，Causal Graphs，52页ppt
因果图，Causal Graphs，52页ppt
专知会员服务
246+阅读 · 2020年4月19日
【NeurlPS2019论文总结】一致收敛可能无法解释深度学习中的泛化现象，Uniform convergence may be unable to explain generalization in deep learning
【NeurlPS2019论文总结】一致收敛可能无法解释深度学习中的泛化现象，Uniform convergence may be unable to explain generalization in deep learning
专知会员服务
14+阅读 · 2019年12月17日
【北京智源大会2019】 神经网络的优化Optimization for Overparametrized Deep Neural Networks，北京大学 | 王立威
【北京智源大会2019】 神经网络的优化Optimization for Overparametrized Deep Neural Networks，北京大学 | 王立威
专知会员服务
22+阅读 · 2019年11月21日
【ICCV 2019 Toturial】Global Optimization for Geometric Understanding with Provable Guarantees（具有可证明保证的几何理解的全局优化）
【ICCV 2019 Toturial】Global Optimization for Geometric Understanding with Provable Guarantees（具有可证明保证的几何理解的全局优化）
专知会员服务
15+阅读 · 2019年11月1日
【ICCV 2019 Workshop】Complete Dictionary Learning via L4-Norm Maximization over the Orthogonal Grou， 加州大学伯克利分校 马毅
【ICCV 2019 Workshop】Complete Dictionary Learning via L4-Norm Maximization over the Orthogonal Grou， 加州大学伯克利分校 马毅
专知会员服务
15+阅读 · 2019年10月31日
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日
热门VIP内容
相关资讯
Hierarchically Structured Meta-learning
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
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日
Disentangled的假设的探讨
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
已删除
已删除
将门创投
4+阅读 · 2018年6月26日
【关关的刷题日记63】Leetcode 111 Minimum Depth of Binary Tree
【关关的刷题日记63】Leetcode 111 Minimum Depth of Binary Tree
专知
6+阅读 · 2017年12月11日
关关的刷题日记13——Leetcode 414. Third Maximum Number
关关的刷题日记13——Leetcode 414. Third Maximum Number
专知
3+阅读 · 2017年10月8日
【学习】Hierarchical Softmax
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
强化学习 cartpole_a3c
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
相关论文
Poising on Ariadne's thread: An algorithm for computing a maximum clique in polynomial time
Arxiv
0+阅读 · 2021年8月30日
Quantum Cross Entropy and Maximum Likelihood Principle
Quantum Cross Entropy and Maximum Likelihood Principle
Arxiv
0+阅读 · 2021年8月26日
Approximation algorithms for the random-field Ising model
Arxiv
0+阅读 · 2021年8月26日
Quasi-upward Planar Drawings with Minimum Curve Complexity
Quasi-upward Planar Drawings with Minimum Curve Complexity
Arxiv
0+阅读 · 2021年8月26日
Adaptively detect and accurately resolve macro-scale shocks in an efficient Equation-Free multiscale simulation
Arxiv
0+阅读 · 2021年8月26日
Dynamic Structural Clustering on Graphs
Arxiv
0+阅读 · 2021年8月26日
Minimum-Distortion Embedding
Arxiv
0+阅读 · 2021年8月24日
Minimal Variance Sampling with Provable Guarantees for Fast Training of Graph Neural Networks
Minimal Variance Sampling with Provable Guarantees for Fast Training of Graph Neural Networks
Arxiv
13+阅读 · 2020年6月24日
Implicit Maximum Likelihood Estimation
Implicit Maximum Likelihood Estimation
Arxiv
7+阅读 · 2018年9月24日
A fast algorithm with minimax optimal guarantees for topic models with an unknown number of topics
Arxiv
7+阅读 · 2018年6月12日
Top
微信扫码咨询专知VIP会员
Top