1 citations · 1 across the 2 of their papers we have counts for
3 papers
An output-sensitive algorithm for all-pairs shortest paths in directed acyclic graphs
Andrzej Lingas, Mia Persson, Dzmitry Sledneu
A straightforward dynamic programming method for the single-source shortest paths problem (SSSP) in an edge-weighted directed acyclic graph (DAG) processes the vertices in a topolo…
Optimal Cuts and Partitions in Tree Metrics in Polynomial Time
Marek Karpinski, Andrzej Lingas, Dzmitry Sledneu
We present a polynomial time dynamic programming algorithm for optimal partitions in the shortest path metric induced by a tree. This resolves, among other things, the exact comple…
Optimal Cuts and Bisections on the Real Line in Polynomial Time
Marek Karpinski, Andrzej Lingas, Dzmitry Sledneu
The exact complexity of geometric cuts and bisections is the longstanding open problem including even the dimension one. In this paper, we resolve this problem for dimension one (t…