学位论文 > 优秀研究生学位论文题录展示

最小化κ限制连通分支数的近似算法

作　者: 吕思远
导　师: 堵丁柱；张国川
学　校: 浙江大学
专　业: 运筹学与控制论
关键词: 图划分 k限制连通分支割点启发式算法近似算法
分类号: O157.5
类　型: 硕士论文
年　份: 2009年
下　载: 17次
引　用: 0次
阅　读: 论文下载

内容摘要

图划分问题是一类有着广泛用途的问题,它在大规模集成电路设计,计算机信息存储方案中均有应用。本文所讨论图划分问题为最小化k限制连通分支数问题：对于任意连通图G=(V,E),给定V上的权重函数ω,对任意整数k,将V划分为尽可能少的互不相交的顶点集{V1,V2,…Vj},使得所有Vi在原图中的诱导子图为连通图,并且权重ω(Vi)≤k。该问题即使对于顶点均为单位权重的简单图仍为N尸一完全问题。已知存在多项式时间精确算法,能够解决该问题限制在树上的情形。对于一般连通图上的极小化k限制连通分支数问题还缺乏相应的近似算法。本文先分析了若干启发式算法对该问题的求解质量问题,指出常见的启发式算法仅考虑顶点间的权重关系,而忽略了对图中割点性质的挖掘。本文进而提出了兼顾割点性质与权重的新启发式算法,并给出其对于二种特殊图近似比分别为4与3的证明。

全文目录

摘要  4-5
Abstract  5-6
目录  6-7
1 第一章概论  7-12
  1.1 组合优化问题概述  7-8
  1.2 图划分问题相关研究进展  8-12
2 第二章最小化k限制连通分支数问题  12-20
  2.1 最小化k限制连通分支数的若干启发式算法分析  12-15
  2.2 新启发式算法性能分析  15-19
  2.3 结论  19-20
参考文献  20-23
致谢  23

最小化κ限制连通分支数的近似算法

内容摘要

全文目录

相似论文