Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > GEOMETRIC METRIC:
Reports tagged with Geometric Metric:
TR12-176 | 14th December 2012
Marek Karpinski, Andrzej Lingas, Dzmitry Sledneu

Optimal Cuts and Partitions in Tree Metrics in Polynomial Time

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 complexity status of the optimal partition problems in one dimensional geometric metric settings. Our method of solution could be also of independent interest ... more >>>




ISSN 1433-8092 | Imprint