Approximation Algorithms for Maximally Balanced Connected Graph Partition
Approximation Algorithms for Maximally Balanced Connected Graph Partition
复制标题
最大平衡连通图划分的近似算法
DOI：
10.1007/s00453-021-00870-3
复制
发表时间：
2019-10
期刊：
影响因子：
1.1
通讯作者：
Zhang An
中科院分区：
文献类型：
--
作者：
Chen Yong;Chen Zhi-Zhong;Lin Guohui;Xu Yao;Zhang An
给定一个连通图，我们寻求对顶点setVintok非空部分进行分区，使得每个部分导出的子图是连接的，并且分区以最小化这些部分的最大基数的方式最大程度地平衡。我们将此问题称为 asmin-max 平衡连通图分区 intokparts 并将其表示为 Ask-BGP。大约四十年前就开始研究这个树问题的顶点加权版本，它采用线性时间精确算法。顶点加权的 2-BGP 和 3-BGPad 分别具有 5/4 近似和 3/2 近似。当 fork-BGP 不存在近似结果时，即顶点未加权变体，除了普通近似之外。在本文中，我们提出了 3-BGP 的另一种 3/2 近似，然后将其扩展为任意固定的 ak/2 近似分叉 BGP。此外，对于 4-BGP，我们提出了改进的 24/13 近似。为此，我们设计了几种局部改进操作，可以在相关的图划分问题中找到更多应用。
Given a connected graph, we seek to partition the vertex setVintoknon-empty parts such that the subgraph induced by each part is connected, and the partition is maximally balanced in the way that the maximum cardinality of thesekparts is minimized. We refer this problem to asmin-max balanced connected graph partitionintokparts and denote it ask-BGP. The vertex-weighted version of this problem on trees has been studied since about four decades ago, which admits a linear time exact algorithm. The vertex-weighted 2-BGPand 3-BGPadmit a 5/4-approximation and a 3/2-approximation, respectively. When, no approximability result exists fork-BGP, i.e., the vertex unweighted variant, except a trivialk-approximation. In this paper, we present another 3/2-approximation for the 3-BGPand then extend it to become ak/2-approximation fork-BGP, for any fixed. Furthermore, for 4-BGP, we propose an improved 24/13-approximation. To these purposes, we have designed several local improvement operations, which could find more applications in related graph partition problems.
登录
查看更多内容
DOI：
10.1142/s0218195903001190
发表时间：
2002-04
期刊：
Int. J. Comput. Geom. Appl.
影响因子：
--
作者：
Mattias Andersson;Joachim Gudmundsson;C. Levcopoulos;G. Narasimhan
通讯作者：
Mattias Andersson;Joachim Gudmundsson;C. Levcopoulos;G. Narasimhan
DOI：
--
发表时间：
2017-05
期刊：
ArXiv
影响因子：
--
作者：
Abdelrahman Madkour;P. Nadolny;Matthew L. Wright
通讯作者：
Abdelrahman Madkour;P. Nadolny;Matthew L. Wright
DOI：
10.1145/322290.322294
发表时间：
1980-07
期刊：
J. ACM
影响因子：
--
作者：
R. I. Becker;Y. Perl;S. Schach
通讯作者：
R. I. Becker;Y. Perl;S. Schach
DOI：
--
发表时间：
2001
期刊：
--
影响因子：
--
作者：
T. Cormen;C. Leiserson;R. Rivest;C. Stein
通讯作者：
T. Cormen;C. Leiserson;R. Rivest;C. Stein
DOI：
10.5465/ambpp.1991.4976828
发表时间：
1991-08
期刊：
--
影响因子：
--
作者：
Jennifer A. Chatman;K. Jehn
通讯作者：
Jennifer A. Chatman;K. Jehn