Optimal Cuts and Partitions in Tree Metrics in Polynomial Time

2012/12/14 by Marek Karpinski, Karpinski, Marek, Andrzej Lingas +3 · 1 citation
Computer Science · Mathematics · #Combinatorics (math.CO) #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC) #cs.CC #cs.DM #cs.DS #math.CO #math.OC

paper · pdf · doi:10.48550/arxiv.1212.3471

arxiv created 2012/12/14 · arxiv updated 2012/12/17

Abstract

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.

Cited by

• Covering Approximate Shortest Paths with DAGs

Related

• Optimal Cuts and Bisections on the Real Line in Polynomial Time
• Optimal Tree Decompositions Revisited: A Simpler Linear-Time FPT Algorithm
• Optimal Parametric Search for Path and Tree Partitioning
• Optimal Partition of a Tree with Social Distance
• Space Saving by Dynamic Algebraization