1 citations · 3 across the 4 of their papers we have counts for
5 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…
A QPTAS for the Base of the Number of Triangulations of a Planar Point Set
Marek Karpinski, Andrzej Lingas, Dzmitry Sledneu
The number of triangulations of a planar n point set is known to be , where the base lies between and The fastest known algorithm for counting triangulations…
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…
A Combinatorial Algorithm for All-Pairs Shortest Paths in Directed Vertex-Weighted Graphs with Applications to Disc Graphs
Andrzej Lingas, Dzmitry Sledneu
We consider the problem of computing all-pairs shortest paths in a directed graph with real weights assigned to vertices. For an 0-1 matrix let be the comp…