Doubly Balanced Connected Graph Partitioning
Doubly Balanced Connected Graph Partitioning
复制标题
双平衡连通图划分
DOI：
10.1145/3381419
复制
发表时间：
2020
影响因子：
1.3
通讯作者：
Zussman, Gil
中科院分区：
文献类型：
--
作者：
Soltan, Saleh;Yannakakis, Mihalis;Zussman, Gil
本文引入并研究了双平衡连通图划分问题：设G =（V，E）是一个连通图，其权（供给/需求）函数p：V→ {−1，+1}满足p（V）=∑j&isinVp（j）= 0.目标是将G划分为（V1，V2），使得G [V1]和G [V2]连通，且对某些常数，最大{<$V1/V2 <$，<$V2/V1 <$} ≤cs.当G是2-连通的时，我们证明了一个满足cp =1和cs =2的解总是存在的，并且可以在随机多项式时间内找到.此外，当G是3-连通的时，我们证明了总有一个“完美”解（一个满足p（V1）=p（V2）=0和0（mod 4）），并且它可以在随机多项式时间内找到.我们的方法可以推广到权重是任意的情况（不一定是±1），以及p（V）≥ 0和超额供给/需求应该平均分配的情况，得到类似的结果。它们也适用于将具有两种类型节点的图划分为两个大的连通子图的问题，这些子图近似地保持两种类型的比例。
We introduce and study the doubly balanced connected graph partitioning problem: LetG=(V,E) be a connected graph with a weight (supply/demand) functionp:V→ {−1, +1} satisfyingp(V)=∑j&isinVp(j) = 0. The objective is to partitionGinto (V1,V2) such thatG[V1] andG[V2] are connected, ∣p(V1)∣,∣p(V2)∣≤cp, and max{ ∣V1/V2∣,∣V2/V1∣} ≤cs, for some constantscpandcs. WhenGis 2-connected, we show that a solution withcp=1 andcs=2 always exists and can be found in randomized polynomial time. Moreover, whenGis 3-connected, we show that there is always a “perfect” solution (a partition withp(V1)=p(V2)=0 and ∣V1∣=∣V2∣, if ∣V∣≡ 0 (mod 4)), and it can be found in randomized polynomial time. Our techniques can be extended, with similar results, to the case in which the weights are arbitrary (not necessarily ±1), and to the case thatp(V)≠ 0 and the excess supply/demand should be split evenly. They also apply to the problem of partitioning a graph with two types of nodes into two large connected subgraphs that preserve approximately the proportion of the two types.
登录
查看更多内容
输电系统级联和脆弱性——运筹学的观点
DOI：
10.1137/1.9781611974164
发表时间：
2015
期刊：
arXiv: Optimization and Control
影响因子：
--
作者：
D. Bienstock
通讯作者：
D. Bienstock
影响因子：
6.6
作者：
Rubén J. Sánchez-García;Max Fennelly;S. Norris;N. Wright;Graham A. Niblo;J. Brodzki;J. Bialek
通讯作者：
Rubén J. Sánchez-García;Max Fennelly;S. Norris;N. Wright;Graham A. Niblo;J. Brodzki;J. Bialek
基于OBDD的大型电力系统分流策略搜索的两阶段方法
DOI：
10.1109/icpst.2002.1047516
发表时间：
2002
期刊：
Proceedings. International Conference on Power System Technology
影响因子：
--
作者：
K. Sun;Qianchuan Zhao;D. Zheng;Jin Ma;Qiang Lu
通讯作者：
Qiang Lu
影响因子：
1.1
作者：
N. Linial;L. Lovász;A. Wigderson
通讯作者：
A. Wigderson
用于三分三连通图和三边连通图的高效算法
DOI：
10.1007/3-540-57899-4_47
发表时间：
1993
期刊：
Proceedings. International Conference on Power System Technology
影响因子：
--
作者：
K. Wada;Kimio Kawaguchi
通讯作者：
Kimio Kawaguchi