| 中文部分 | 第1-70页 |
| 中文摘要 | 第7-10页 |
| 英文摘要 | 第10-14页 |
| 符号说明 | 第14-15页 |
| 第一章 绪论 | 第15-20页 |
| §1.1 动机与背景 | 第15-16页 |
| §1.2 算法的基本概念 | 第16-18页 |
| §1.3 论文概要 | 第18-20页 |
| 第二章 推广的设施选址问题 | 第20-27页 |
| §2.1 引言 | 第20-21页 |
| §2.2 问题的陈述 | 第21-22页 |
| §2.3 整数规划模型 | 第22-24页 |
| §2.4 辅助的设施选址问题 | 第24-25页 |
| §2.5 算法的设计与分析 | 第25-26页 |
| §2.6 结束语 | 第26-27页 |
| 第三章 费用分配问题 | 第27-32页 |
| §3.1 引言 | 第27页 |
| §3.2 线性规划模型 | 第27-29页 |
| §3.3 算法 | 第29-31页 |
| §3.4 结束语 | 第31-32页 |
| 第四章 推广的Steiner树-星问题 | 第32-40页 |
| §4.1 引言 | 第32-33页 |
| §4.2 基于CFLP的算法 | 第33-34页 |
| §4.2.1 度量的无容量的设施选址问题 | 第33-34页 |
| §4.2.2 连通的设施选址问题 | 第34页 |
| §4.3 基于UFLP的算法 | 第34-36页 |
| §4.4 算法的分析 | 第36-37页 |
| §4.5 其它相关的Steiner问题 | 第37-39页 |
| §4.5.1 k-MST问题 | 第38页 |
| §4.5.2 Prize-collecting Steiner树问题 | 第38页 |
| §4.5.3 k-Steiner树问题 | 第38-39页 |
| §4.6 结束语 | 第39-40页 |
| 第五章 瓶颈Steiner网络设计问题 | 第40-46页 |
| §5.1 引言 | 第40-41页 |
| §5.1.1 问题的陈述 | 第40-41页 |
| §5.1.2 背景 | 第41页 |
| §5.2 基于GSP的算法 | 第41-42页 |
| §5.3 算法 | 第42-45页 |
| §5.3.1 预备知识 | 第42-43页 |
| §5.3.2 有根情形的BSNDP的算法 | 第43-45页 |
| §5.3.3 无根情形的BSNDP的算法 | 第45页 |
| §5.4 结束语 | 第45-46页 |
| 第六章 分组和覆盖Steiner问题 | 第46-52页 |
| §6.1 引言 | 第46-48页 |
| §6.1.1 问题的陈述 | 第46页 |
| §6.1.2 假设 | 第46-48页 |
| §6.2 从一般图到树 | 第48页 |
| §6.3 从一般图到平面图 | 第48-49页 |
| §6.4 USP与CSP的转化 | 第49页 |
| §6.5 含退化组的GSP | 第49-50页 |
| §6.6 小组数的CSP | 第50页 |
| §6.7 一个相关问题 | 第50-51页 |
| §6.8 结束语 | 第51-52页 |
| 第七章 断点Median问题 | 第52-58页 |
| §7.1 引言 | 第52-53页 |
| §7.2 基因组的图论描述 | 第53-55页 |
| §7.3 TSP的近似算法 | 第55-56页 |
| §7.4 环形基因组情形的BMP | 第56页 |
| §7.4.1 将BMP转化为TSP | 第56页 |
| §7.4.2 近似算法 | 第56页 |
| §7.5 线形基因组情形的BMP | 第56-57页 |
| §7.6 结束语 | 第57-58页 |
| 参考文献 | 第58-66页 |
| 致谢 | 第66-67页 |
| 作者简介 | 第67-69页 |
| 学位论文评阅及答辩情况表 | 第69-70页 |
| 英文部分 | 第70-146页 |
| 中文摘要 | 第78-81页 |
| Abstract | 第81-85页 |
| Notation Index | 第85-86页 |
| Chapter 1.Introduction | 第86-92页 |
| §1.1 Motivation and background | 第86-88页 |
| §1.2 Some key concepts of algorithm | 第88-90页 |
| §1.3 Thesis outline | 第90-92页 |
| Chapter 2.Generalized Facility Location Problem | 第92-100页 |
| §2.1 Introduction | 第92-94页 |
| §2.2 Problem statement | 第94页 |
| §2.3 Integer program formulation | 第94-96页 |
| §2.4 Auxiliary facility location problem | 第96-97页 |
| §2.5 Algorithmic design and analysis | 第97-99页 |
| §2.6 Conclusion | 第99-100页 |
| Chapter 3.The Cost Allocation Problem | 第100-105页 |
| §3.1 Introduction | 第100-101页 |
| §3.2 Linear program formulation | 第101-102页 |
| §3.3 Algorithm | 第102-104页 |
| §3.4 Conclusion | 第104-105页 |
| Chapter 4.Generalized Steiner Tree-star Problem | 第105-114页 |
| §4.1 Introduction | 第105-107页 |
| §4.2 CFLP-based algorithm | 第107-108页 |
| §4.2.1 The metric uncapacitated facility location problem | 第107页 |
| §4.2.2 The connected facility location problem | 第107-108页 |
| §4.3 UFLP-based algorithm | 第108-110页 |
| §4.4 Algorithmic analysis | 第110-111页 |
| §4.5 Other related Steiner problems | 第111-113页 |
| §4.5.1 k-MST problem | 第111-112页 |
| §4.5.2 Prize-collecting Steiner tree problem | 第112-113页 |
| §4.5.3 k-Steiner tree problem | 第113页 |
| §4.6 Conclusion | 第113-114页 |
| Chapter 5.The Bottleneck Steiner Network Design Problem | 第114-121页 |
| §5.1 Introduction | 第114-116页 |
| §5.1.1 Problem statement | 第114-115页 |
| §5.1.2 Backgroud | 第115-116页 |
| §5.2 GSP-based algorithm | 第116-117页 |
| §5.3 Algorithm | 第117-120页 |
| §5.3.1 Preliminaries | 第117-118页 |
| §5.3.2 Algorithm for the rooted case of BSNDP | 第118-120页 |
| §5.3.3 Algorithm for the unrooted case of BSNDP | 第120页 |
| §5.4 Conclusion | 第120-121页 |
| Chapter 6.The Group and Covering Steiner Problems | 第121-128页 |
| §6.1 Introduction | 第121-123页 |
| §6.1.1 Problem statement | 第121-122页 |
| §6.1.2 Assumptions | 第122-123页 |
| §6.2 From general graphs to trees | 第123-124页 |
| §6.3 From general graphs to planar graphs | 第124-125页 |
| §6.4 Transformation between GSP and CSP | 第125页 |
| §6.5 GSP with degenerate groups | 第125-126页 |
| §6.6 CSP with small number of groups | 第126-127页 |
| §6.7 A related problem | 第127页 |
| §6.8 Conclusion | 第127-128页 |
| Chapter 7.The Breakpoint Median Problem | 第128-135页 |
| §7.1 Introduction | 第128-129页 |
| §7.2 Graph-theoretic representation of genomes | 第129-131页 |
| §7.3 Approximation algorithms for TSP | 第131-132页 |
| §7.4 BMP for the circular genomes | 第132-133页 |
| §7.4.1 Reduce BMP to TSP | 第132-133页 |
| §7.4.2 Approximation algorithm | 第133页 |
| §7.5 BMP for the linear genomes | 第133-134页 |
| §7.6 Conclusion | 第134-135页 |
| Bibliography | 第135-143页 |
| Acknowledgements | 第143-144页 |
| Curriculum Vitae | 第144-146页 |
| 学位论文评阅及答辩情况表 | 第146页 |
