4 citations · 10 across the 24 of their papers we have counts for
3 papers · 1 filter
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…
A fast parallel algorithm for minimum-cost small integral flows
Andrzej Lingas, Mia Persson
We present a new approach to the minimum-cost integral flow problem for small values of the flow. It reduces the problem to the tests of simple multi-variate polynomials over a fin…
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…