Rheinische Friedrich-Wilhelms-Universität Bonn Institut für Informatik
 
Abteilung V

 
Universität Bonn -> Institut für Informatik -> Abteilung V
CS-APX-Reports 2012 Copyright 2012 Universität Bonn, Institut für Informatik, Abt. V
89141

14.12.2012

Optimal Cuts and Partitions in Tree Metrics in Polynomial Time
Marek Karpinski, Andrzej Lingas and Dzmitry Sledneu
[Download PostScript] [Download PDF]

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 in other applications. We discuss also an extension of our method to the class of metrics induced by the bounded treewidth graphs.

Last Change: 11/05/14 at 10:58:44
 English
Universität Bonn -> Institut für Informatik -> Abteilung V

Powered by Zope