共查询到20条相似文献,搜索用时 62 毫秒
1.
2.
研究了源于无线网状网络的度数有界最大支撑子图问题:给定连通图G=(V,E)和正整数d≥2,求G的一个最大支撑子图H,满足对V中每个顶点v,v在H中的度数dH(v)不超过d。这里,支撑子图指图G的一个连通而且包括G中所有顶点的子图。就输入图的边是否带权,分别设计了多项式时间近似算法。当输入图为无权图时,证明了近似算法的近似比为2;当输入图为赋权图时,证明了算法输出一个最大度数不超过d+1、权重不低于最优解权重1/(d+2)的支撑子图。算法输出的度数有界支撑子图可以用作无线网状网络的传输子网。 相似文献
3.
在计算机互连网络中,完全独立生成树在信息的可靠传输、并行传输、安全分发等方面具有重要的作用。假设图G中存在n棵生成树T1,T2,…,Tn,若对于图G中任意两个顶点u和v,满足u和v之间的路径在这n棵树中都是顶点不相交的,则称这n棵树为完全独立生成树(CISTs)。在2015年,Chang等人证明了对于包含n(n≥6)个顶点的任意图G,如果图G的最小顶点度数至少为n-2,那么,G中存在至少 n/3 棵CISTs[1]。在Chang等人的基础上,文中继续深入研究了图G中顶点度数和CISTs的棵数之间的关系。对于包含n(n≥5) 个顶点的任意图G,假设图G的最小顶点度数至少为n-2,得出度数为n-2的顶点的个数、度数为n-1的顶点的个数与图G中CISTs的棵数之间关系的推导等式,并证明了其正确性,从而改进了文献[1]中的结果。 相似文献
4.
5.
6.
研究内部节点受限的最小生成树问题:给定一个赋权无向完全图[G=V,E],假定[w:E→R+]为边集[E]的权重函数且满足三角不等式,给定点集[V]的一个子集[RR?V],目标是寻找图[G]的一个满足[R]中的点皆为内部顶点的权重最小的生成树。由于该问题是[NP-]困难的,提出了一个伪多项式时间最优算法,设计了一个近似比为2的多项式时间近似算法,并且给出例子以说明该近似比是紧的。 相似文献
7.
8.
无线网络中的虚拟骨干(VB)是一些无线节点的子集,因此只有VB中的节点负责路由相关任务,并且VB总权值越小会导致开销越少。在一个点赋权的无线网络中,不单要考虑VB中节点数的多少,更重要的是要考虑其总权值的大小。通常,一个赋权无线网络被模型化为一个点赋权单位圆盘图(UDG),相应地赋权无线网络中的最小权VB问题被抽象为点赋权UDG中的最小权连通控制集(MWCDS)问题进行研究。求MWCDS是一个NP-难问题。为降低点赋权UDG中MWCDS问题的近似比,在连通部分提出一种新方法——基于度的点赋权Steiner树算法。结合目前最好的结果,对于UDG中的MWCDS问题将得到一个(3.32+ε)-近似算法。同样地,对于UDG中的最小权顶点覆盖(MWCVC)问题也将得到一个(3.32+ε)-近似算法。证明了通过改进连通部分的近似比令点赋权UDG中MWCDS问题的近似比降低的方法是可行的。 相似文献
9.
基于一种新的边权编码方案的中国邮递员问题的DNA计算模型 总被引:4,自引:0,他引:4
权编码方法是DNA计算中一个重要且有挑战性的问题.设计了一种新的用于表示赋权图中边权的DNA编码方案,给出了用该方案求解中国邮递员问题的DNA算法,并利用Markov链分析了DNA算法中生成各种路径的随机过程.对于任一赋权图G=(V,E),首先通过边到点映射把它转换为广义边图G'=(V',E').图G的每条边ei被分别映射为图G'的一个顶点(v'i).若G中ei与ej邻接,则连接G1中v'i和v'j.若G中vi为奇顶点,则在与vi关联的边对应的G'的顶点上添加自环.用于编码顶点v'i的DNA串si的长度等于边ei的权值.用于编码边v'i v'j的DNA串sij为si的后半部分与sj的前半部分并置后的逆补.所提出的DNA编码方案具有易于编码、易于推广且错误率低的特点.该工作可提高DNA计算中表示和处理数值的能力,扩展DNA计算求解最优化问题的范围. 相似文献
10.
传感器网络中高效的最小连通支配集求解算法 总被引:1,自引:1,他引:0
在无线传感器网络中,连通支配集被广泛应用于构建虚拟主干。由于求解最小连通支配集是一个NP难问题,许多近似算法被提出用于构建可用的最小连通支配集。针对当前近似算法存在的不足,我们提出了一个新的分布式近似构造算法—CDS-HG,该算法用层次图对无线传感器网络进行建模,算法用基于竞争的贪心策略从每一层选出最少的节点去支配下一层的所有节点。理论分析和模拟结果表明,CDS-HG算法产生的连通支配集是目前最小,并且其消息复杂度也是目前最低的。 相似文献
11.
组合优化问题反问题的研究进展 总被引:1,自引:0,他引:1
本文重点介绍了组合优化问题反问题的研究进展。具体内容包括:线性规划问题反问题、最短路问题反问题、最小费用流问题反问题和网络容量扩充问题反问题的提出背景、研究成果、应用前景及一些可能的研究方向。 相似文献
12.
13.
14.
Javad Akbari Torkestani 《人工智能实验与理论杂志》2016,28(3):499-527
In this article, a generalisation of the vertex colouring problem known as bandwidth multicolouring problem (BMCP), in which a set of colours is assigned to each vertex such that the difference between the colours, assigned to each vertex and its neighbours, is by no means less than a predefined threshold, is considered. It is shown that the proposed method can be applied to solve the bandwidth colouring problem (BCP) as well. BMCP is known to be NP-hard in graph theory, and so a large number of approximation solutions, as well as exact algorithms, have been proposed to solve it. In this article, two learning automata-based approximation algorithms are proposed for estimating a near-optimal solution to the BMCP. We show, for the first proposed algorithm, that by choosing a proper learning rate, the algorithm finds the optimal solution with a probability close enough to unity. Moreover, we compute the worst-case time complexity of the first algorithm for finding a 1/(1–?) optimal solution to the given problem. The main advantage of this method is that a trade-off between the running time of algorithm and the colour set size (colouring optimality) can be made, by a proper choice of the learning rate also. Finally, it is shown that the running time of the proposed algorithm is independent of the graph size, and so it is a scalable algorithm for large graphs. The second proposed algorithm is compared with some well-known colouring algorithms and the results show the efficiency of the proposed algorithm in terms of the colour set size and running time of algorithm. 相似文献
15.
G. Scheithauer 《International Transactions in Operational Research》1999,6(2):199-213
New relaxations are developed in this paper for problems of optimal packing of small (rectangular-shaped) pieces within one or several larger containers. Based on these relaxations tighter bounds for the Container Loading Problem (CLP) and the Multi-Container Loading Problem (MCLP) are obtained.
The new relaxations for the CLP and MCLP lead to linear programming problems. A corresponding solution approach is discussed which is based on a column generation technique. Results of computational tests are also given. 相似文献
The new relaxations for the CLP and MCLP lead to linear programming problems. A corresponding solution approach is discussed which is based on a column generation technique. Results of computational tests are also given. 相似文献
16.
一种求解划分问题的新算法 总被引:1,自引:0,他引:1
郝志峰 《计算机辅助设计与图形学学报》2000,12(7):544-547
划分问题是VLSI-CAD设计中的基本问题,针对近似划分问题、划分问题、背包问题,提出了一种行之有效的快速算法,其核心思想是基于拟物思路构造目标函数。 相似文献
17.
18.
Jang-Ping SheuChun-Lien WuGen-Huey Chen 《Parallel Computing》1989,11(3):381-384
In this paper, algorithms are proposed for finding the first k largest numbered processes in hypercubes with and without faulty nodes. 相似文献
19.
20.
本文介绍了赋权诱导推理的基本概念及其求解算法复杂性研究的现状。诱导推理在人工智能领域有广泛的应用前景,但现有的求解算法都未能从根本上排除NP-难解性的困扰,本文考虑了其中一类子问题;二阶独立赋权诱导问题,并给出求出其最优解的多项式时间算法。 相似文献