数据传输选择问题:算法设计和复杂性分析

摘要

数据和信息传输业务对网络的要求越来越高,在满足实时性、可靠性的同时,还要求充分利用网络资源,降低传输成本.文章首先建立了数据传输网络选择的最小成本模型,给出了有效支撑树代表集的概念,并给出了一个时间复杂性为0(mlog n)的算法产生代表集,其中m,n分别代表网络的边数和顶点数.然后对静态数据传输支撑树问题和动态数据传输支撑树问题,分别给出了一个时间复杂性为D(mlog n)和0(m2+mlog n)的多项式时间的好算法.