.png){kind=icon}
返回
.png){kind=icon}
.png){kind=icon}
.png){kind=icon}
.png){kind=icon}
.png){kind=icon}
摘要
En 中文
We introduce and study the doubly balanced connected graph partitioning problem: Let
G
=(
V
,
E
) be a connected graph with a weight (supply/demand) function
p
:
V
→ {−1, +1} satisfying
p
(
V
)=∑
j
&isin
V
p
(
j
) = 0. The objective is to partition
G
into (
V
1
,
V
2
) such that
G
[
V
1
] and
G
[
V
2
] are connected, ∣
p
(
V
1
)∣,∣
p
(
V
2
)∣≤
c
p
, and max{ ∣
V
1
/
V
2
∣,∣
V
2
/
V
1
∣} ≤
c
s
, for some constants
c
p
and
c
s
. When
G
is 2-connected, we show that a solution with
c
p
=1 and
c
s
=2 always exists and can be found in randomized polynomial time. Moreover, when
G
is 3-connected, we show that there is always a “perfect” solution (a partition with
p
(
V
1
)=
p
(
V
2
)=0 and ∣
V
1
∣=∣
V
2
∣, 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 that
p
(
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.
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
暂无期刊信息
机构
暂无机构信息
引用论文
暂无论文信息