4 citations · 5 across the 6 of their papers we have counts for
Showing 2012Show all
3 papers · 1 filter
cs.DS2012
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…
cs.DC2012
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…
cs.DS2012★ 1 cited
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…