کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
428973 | 686978 | 2013 | 5 صفحه PDF | دانلود رایگان |
• A novel polynomial time dynamic programming algorithm for optimal partitions in the shortest path metric induced by a tree.
• A resolution of the exact complexity status of the optimal partition problems in one-dimensional geometric metric settings.
• A discussion of an extension of our method to the class of metrics induced by the bounded treewidth graphs.
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.
Journal: Information Processing Letters - Volume 113, Issue 12, 30 June 2013, Pages 447–451