Proof. In the following, to avoid cumbersome notation, we assume that the constants in the exponent of
2
O(ω(u))
are 1, i.e., that the algorithm spends 2
ω(u)
· n
O(1)
time at u, and makes 2
ω(u
i
)
recursive calls. It is
easy to see that any other constants in the exponent is absorbed in the exponent of 2
O(n
1−1/d
)
.
Consider node u ∈ V (F ). We will inductively prove that the overall running time of A corresponding to
one recursive call on u is upper bounded by `(u) · n
O(1)
· max
π
u
2
2ω(π
u
)
, where `(u) is the number of leaves in
the subtree of F rooted at u, and the maximum is taken over all root-leaf paths π
u
in the subtree rooted
at u. Assuming this claim is true, then the bound on the running time holds as follows. The running time
of A corresponding to the root r of F is upper bounded by n · n
O(1)
· max
π
2
2ω(π)
, where the maximum
is taken over all root-leaf paths in F . However, 2
2ω(π)
is at most 2
O(wtd(G
P
))
, which is at most 2
O(n
1−1/d
)
.
Furthermore, if the algorithm uses polynomial space at every node in V (F ), and since the (unweighted)
depth of F is at most n, it only uses polynomial space overall.
Now we prove the inductive claim. Fix a node u ∈ V (F ). If u is leaf in the tree, then the running
time is upper bounded by 2
ω(u)
· n
O(1)
by the property of A. Note that `(u) = 1 in this case. Now,
suppose u is an arbitrary internal node in V (F ). The algorithm spends time proportional to 2
ω(u)
· n
O(1)
,
and makes at most 2
ω(u)
recursive calls on the children of u. Let C(u) denote the set of children of u.
By the inductive hypothesis, time taken by A in one recursive call at any child v
i
∈ C(u) is bounded by
`(v
i
) · n
O(1)
· max
π
v
i
2
2ω(π
v
i
)
, where the maximum is taken over all v
i
-leaf paths π
v
i
in the subtree rooted at v
i
.
Therefore, the overall running time at u is bounded by
T (u) ≤ 2
ω(u)
· n
O(1)
+ 2
ω(u)
·
X
v
i
∈C(u)
`(v
i
) · n
O(1)
· max
π
v
i
2
2ω(π
v
i
)
≤ n
O(1)
·
2
ω(u)
+
X
v
i
∈C(u)
`(v
i
) · max
π
v
i
2
ω(u)+2ω(π
v
i
)
≤ `(u) · n
O(1)
·
2
ω(u)
+ max
π
u
2
ω(u)+2ω(π
v
i
)
(Since there are at most `(u) paths π
u
going from u to a leaf)
≤ `(u) · n
O(1)
· max
π
u
2
2ω(π
u
)
.
3 Simple Recursive Algorithms
Independent Set
Recall that the task of the Independent Set problem is, given a graph G, to find an independent set, i.e., a
set of pairwise nonadjacent vertices, of maximum size. Given G = (V, E), we first obtain (G, d, P, G
P
), and
associated (F, ϕ) of weighted treedepth O(n
1−1/d
) in 2
O(n
1−1/d
)
time and polynomial space using Theorem
1 We have the following simple observation from [4].
Observation 1 ([4]). Let P be a κ-partition of G = (V, E), and let I ⊆ V (G) be an independent set. Then,
|I ∩ V
i
| ≤ κ for any V
i
∈ P.
We now describe our recursive algorithm. In addition to (G, d, P, G
P
), and (F, ϕ), the algorithm takes
input u ∈ V (F ), and D ⊆ V (G). Here, u is the current node in V (F ) in the recursive algorithm, and
D ⊆ V (G) denotes the set of disallowed vertices that cannot be added to the independent set, due to
previous choices made by the algorithm.
Let ϕ(u) = V
i
∈ P be the associated part in the κ-partition P, and define I
u
be the collection of subsets
I ⊆ V
i
such that (1) I is independent in G, (2) I ∩ F = ∅, and (3) |I| ≤ κ. For each guess I ∈ I
u
, we call the
algorithm recursively on the children of u, where the set of disallowed nodes is updated to D
0
← D ∪ N
G
(I).
For a child v
j
of u, let MaxIS(v
j
, I) denote the independent set returned by the algorithm corresponding to
guess I. We return the independent set maximizing |I ∪
S
v
j
∈C(u)
MaxIS(v
j
, I)| over all I ∈ I
u
. It is easy
6
剩余29页未读，继续阅读
易小侠
- 粉丝: 6545
- 资源: 9万+
我的内容管理
展开
最新资源
- 贵州煤矿矿井水分类与处理策略：悬浮物、酸性与非酸性
- 醛固酮增多症肾上腺静脉采样对比：ACTH后LR-CAV的最优评估
- 开源云连接传感器监控平台：农业土壤湿度远程监测
- 母婴用品企业年度生产计划线性规划优化模型：实证与应用
- 井下智能变电站：Rogowski线圈电流检测系统的研发与性能验证
- 霍州矿区煤巷稳定性分析及支护策略
- ARM嵌入式系统远程软件更新方案：基于TFTP协议
- 煤炭选煤中汞分布规律与洗选脱汞效果
- 提升码垛机器人性能：拉格朗日动力学模型与滑模模糊控制的应用
- 增强现实技术提升学前手写教学：设计与开发案例
- 不规则工作面沉陷三角剖分算法提升与应用
- 卡尔曼滤波在瞬变电磁干扰压制中的应用研究
- 煤矿安全能力研究：理论与系统构建
- LonWorks总线技术在斜巷运输车辆定位与跑车防护中的应用
- 神东煤炭集团高效煤粉锅炉系统：节能环保新实践
- Ti/SnO2+Sb2Ox/PbO2电极分形维数与电催化性能研究
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
