[PDF][PDF] New additive approximations for shortest paths and cycles
49th International Colloquium on Automata, Languages, and Programming (ICALP …, 2022•par.nsf.gov
This paper considers additive approximation algorithms for All-Pairs Shortest Paths (APSP)
and Shortest Cycle in undirected unweighted graphs. The results are as follows: We obtain
the first+ 2-approximation algorithm for APSP in n-vertex graphs that improves upon Dor,
Halperin and Zwick's (SICOMP'00) O (n7/3) time algorithm. The new algorithm runs in O (n2.
29) time and is obtained via a reduction to Min-Plus product of bounded difference matrices.
We obtain the first additive approximation scheme for Shortest Cycle, generalizing the …
and Shortest Cycle in undirected unweighted graphs. The results are as follows: We obtain
the first+ 2-approximation algorithm for APSP in n-vertex graphs that improves upon Dor,
Halperin and Zwick's (SICOMP'00) O (n7/3) time algorithm. The new algorithm runs in O (n2.
29) time and is obtained via a reduction to Min-Plus product of bounded difference matrices.
We obtain the first additive approximation scheme for Shortest Cycle, generalizing the …
Abstract
This paper considers additive approximation algorithms for All-Pairs Shortest Paths (APSP) and Shortest Cycle in undirected unweighted graphs. The results are as follows: We obtain the first+ 2-approximation algorithm for APSP in n-vertex graphs that improves upon Dor, Halperin and Zwick’s (SICOMP’00) O (n7/3) time algorithm. The new algorithm runs in O (n2. 29) time and is obtained via a reduction to Min-Plus product of bounded difference matrices.
We obtain the first additive approximation scheme for Shortest Cycle, generalizing the approximation algorithms of Itai and Rodeh (SICOMP’78) and Roditty and Vassilevska W.(SODA’12). For every integer r≥ 0, we give an O (n+ n2+r/mr) time algorithm that returns a+(2r+ 1)-approximate shortest cycle in any n-vertex, m-edge graph.
par.nsf.gov
以上显示的是最相近的搜索结果。 查看全部搜索结果