网络优化中支撑树的新模型—算法和复杂性

摘要

该文主要研究了几个支撑树上的新优化模型.这些模型可以划分为两类,一类是完全新模型,如多参数最小树模型、Hamming长度的最小树问题的逆问题等.另一类是老问题的新研究,如最短路树的优化、计数、和产生等问题.该文主要包括五章.第一章是绪论,包括三节.第一节介绍了网络中的一些基本概念,给出了该文中一些符号的含义.第二节介绍了最短路问题及主要算法,包括Dijkstra算法、Fredman算法、Ford算法、Floyd算法等.第三节介绍了最小树问题及主要算法,包括Kruskal算法、Dijkstra算法、Yao算法、Prim算法等.第一章的最后部分介绍了度约束最小树问题,定义了k-度约束最小树问题,并证明了存在一个k<'*>,1≤n,使当k时,k-度约束最小树问题是多项式时间内可解的,否则k-度约束最小树问题是NP-完全的.第二章是最短路网络与最短路树,包括四节.第三章是最短路树的相关问题,包括三节.第四章是Robust支撑树问题,包括两节.第一章是多参数最小树问题.在该节中,利用划分问题的NP-完全性,证明了多参数最小树问题是NP-完全的;利用Greedy算法和Fisher算法,给出了问题的上下界估计;给出了一个近似算法并分析了其性能比;最后同样利用划分问题的NP-完全性,证明了最大最小后悔支撑树问题也是NP-完全的.第二节是最小树问题的逆问题.在该节中,建立了最小树问题的逆问题模型,将Hamming长度下的模型转化成二分图中的最小顶点覆盖问题,从而用匈牙利方法给出了一个算法,时间复杂性为O(mn<'2>).最后将Hamming长度和L<,1>长度组合在一起,形成了一个双目标优化问题,从而提出了一个新open问题.第五章是支撑树的序列产生问题,包括四节.第一节是基本概念.第二节是支撑树的树长分布.在该节中,给出了支持树树长分布定义,并利用子集和问题的复杂性证明了求支撑树树长分布L(G)问题是NP-完全的.第三节是严格第k最小树问题,对k=2的特殊情况给出了一个多项式算法.第四节是最小树的产生和一些相关问题.该节研究了最小树网络、支撑树的连通性以及由于边的删除最小树的长度变动情况.

目录

文摘

英文文摘

前言

第一章绪论

第一节网络中的一些基本概念

第二节最短路问题及主要算法

第三节最小支撑树问题及主要算法

第二章最短路网络与最短路树

第一节最短路网络及应用

第二节最短路树与最小最短路树

第三节最短路树的计数

第四节最短路树的序列产生

第三章最短路树的相关问题

第一节完全最短路树及相关问题

第二节Pendants-median支撑树问题

第三节最短路树的相关问题

第四章Robust支撑树问题

第一节多参数最小支撑树问题

第二节最小树问题的逆问题

一 动边最小树逆问题

二 动长最小树问题的逆问题

三 双目标最小树逆问题和L2长度下的最小树逆问题

第五章支撑树的序列产生问题

第一节基本概念

第二节支撑树的树长分布

第三节严格第k最小支撑树问题

附录Ⅰ参考文献

附录Ⅱ读博士期间完成的论文

附录Ⅲ与本文有关的open问题