论文标题
分区加权树和仙人掌图的算法
Partitioning algorithms for weighted trees and cactus graphs
论文作者
论文摘要
在本文中，我们考虑了加权树和仙人掌图的不同约束分区问题。我们专注于（L，U）分区问题，这是将加权图分配到连接的簇中的问题，使每个群集都满足下部和上部权重约束L和U。已知将最小，最大或固定数量的簇分配为NP固定，但可以在树上溶解多项式时间。我们证明，（L，U）分区问题的这三个变体也可以通过呈现多项式时间算法来解决仙人掌图。此外，我们提出了一种计算相应分区的有效方法。对于其他优化目标或其他约束，分区问题也变成了NP -HARD-即使在树上，重量较低，等于零。我们表明，我们的方法可以用作算法框架，以使用假poly液运行时解决加权树和仙人掌图的其他分区问题。
In this paper, we consider different constrained partition problems for weighted trees and cactus graphs. We focus on the (l,u)-partition problem, which is the problem of partitioning a weighted graph into connected clusters such that each cluster fulfills the lower and upper weight constraints l and u. Partitioning into a minimum, maximum or a fixed number of clusters is known to be NP-hard in general, but polynomial-time solvable on trees. We prove that these three variants of the (l,u)-partition problem can be solved for cactus graphs as well by presenting a polynomial-time algorithm. Additionally, we present an efficient method to compute the corresponding partitions. For other optimization goals or additional constraints, the partition problem becomes NP-hard - even on trees and for a lower weight bound equal to zero. We show that our method can be used as an algorithmic framework to solve other partition problems for weighted trees and cactus graphs with a pseudopolynomial runtime.
