检索结果-内蒙古大学图书馆

efficient parameterized algorithms for computing all-pairs shortest paths

DISCRETE APPLIED MATHEMATICS 2023年第1期341卷 102-119页

作者： Kratsch, Stefan Nelles, Florian Humboldt Univ Unter Linden 6 D-10099 Berlin Germany

Computing for all pairs of vertices the shortest paths in a graph is a fundamental and much-studied problem with many applications. Unfortunately, despite intense study, there are still no significantly faster algorithms for it than the O(n(3)) time algorithm due to Floyd and Warshall (1962). Somewhat faster algorithms exist for the vertex-weighted version if fast matrix multiplication may be used. Yuster (SODA 2009) gave an algorithm running in time O(n(2.842)), but no combinatorial, truly subcubic algorithm is known. Motivated by the recent framework of efficient parameterized algorithms (or '' FPT in P ''), we investigate the influence of the graph parameters clique-width (cw) and modular-width (mw) on the running times of algorithms for solving vertex-weighted all-pairs shortest paths. We obtain efficient (and combinatorial) parameterized algorithms of times O(cw(2)n(2)), resp. O(mw(2)n + n(2)). If fast matrix multiplication is allowed then the latter can be improved to O(mw(1.842)n+ n(2)) using the algorithm of Yuster as a black box. The algorithm relative to modular-width is adaptive, meaning that the running time matches the best unparameterized algorithm for parameter value mw equal to n, and outperforms it already for mw epsilon O(n(1-epsilon)) for any epsilon > 0. (c) 2023 Elsevier B.V. All rights reserved.

关键词： All-pairs shortest paths efficient parameterized algorithms parameterized complexity Clique-width Modular-width

来源：评论

学校读者我要写书评

暂无评论

efficient parameterized algorithms for Computing All-Pairs Shortest Paths 37

Efficient Parameterized Algorithms for Computing All-Pairs S...

引用

37th International Symposium on Theoretical Aspects of Computer Science (STACS)

作者： Kratsch, Stefan Nelles, Florian Humboldt Univ Berlin Germany

ISBN: (纸本)9783959771405

Computing all-pairs shortest paths is a fundamental and much-studied problem with many applications. Unfortunately, despite intense study, there are still no significantly faster algorithms for it than the O(n(3)) time algorithm due to Floyd and Warshall (1962). Somewhat faster algorithms exist for the vertex-weighted version if fast matrix multiplication may be used. Yuster (SODA 2009) gave an algorithm running in time O(n(2.842)) , but no combinatorial, truly subcubic algorithm is known. Motivated by the recent framework of efficient parameterized algorithms (or "FPT in P"), we investigate the influence of the graph parameters clique-width (cw) and modular-width (mw) on the running times of algorithms for solving ALL-PAIRS SHORTEST PATHS. We obtain efficient (and combinatorial) parameterized algorithms on non-negative vertex-weighted graphs of times O(cw(2) n(2)), resp. O(mw(2) n(2)). If fast matrix multiplication is allowed then the latter can be improved to O( mw(1.842) n + n(2)) using the algorithm of Yuster as a black box. The algorithm relative to modular-width is adaptive, meaning that the running time matches the best unparameterized algorithm for parameter value mw equal to n, and they outperform them already for mw is an element of O(n(1-epsilon)) for any epsilon > 0.

关键词： All-pairs shortest Paths efficient parameterized algorithms parameterized Complexity Clique-width Modular-width

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：