首页> 外文期刊>Algorithmica >A Faster Algorithm for Computing the Principal Sequence of Partitions of a Graph
【24h】

A Faster Algorithm for Computing the Principal Sequence of Partitions of a Graph

机译:计算图的主分区序列的更快算法

获取原文
获取原文并翻译 | 示例

摘要

We consider the following problem: given an undirected weighted graph G=(V,E,c) with nonnegative weights, minimize function c(δ(Π))−λ|Π| for all values of parameter λ. Here Π is a partition of the set of nodes, the first term is the cost of edges whose endpoints belong to different components of the partition, and |Π| is the number of components. The current best known algorithm for this problem has complexity O(|V|2) maximum flow computations. We improve it to |V| parametric maximum flow computations. We observe that the complexity can be improved further for families of graphs which admit a good separator, e.g. for planar graphs. Keywords Principal sequence of partitions - Network attack - Network strength - Minimum cut/maximum flow - Parametric algorithm
机译:我们考虑以下问题:给定具有非负权重的无向加权图G =(V,E,c),将函数c(δ(Π))-λ|Π|最小化。对于参数λ的所有值。这里Π是节点集合的一个分区,第一项是其端点属于该分区的不同组件的边的成本,||||。是组件的数量。当前针对该问题的最著名算法具有复杂度O(| V | 2 )最大流量计算。我们将其改进为| V |参数最大流量计算。我们观察到,对于允许使用良好分隔符的图族来说,可以进一步提高复杂度。用于平面图。分区的主要顺序-网络攻击-网络强度-最小割/最大流量-参数算法

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号