检索结果-南通市图书馆

Algorithms for the Prize-Collecting k-steiner tree Problem

在线全文

学校读者我要写书评

暂无评论

Tsinghua Science and Technology 2022年第5期27卷 785-792页

作者： Lu Han Changjun Wang Dachuan Xu Dongmei Zhang School of Science Beijing University of Posts and TelecommunicationsBeijing 100876China Academy of Mathematics and Systems Science Chinese Academy of SciencesBeijing 100190China Beijing Institute for Scientific and Engineering Computing Beijing University of TechnologyBeijing 100124China School of Computer Science and Technology Shandong Jianzhu UniversityJinan 250101China

In this paper,we study the prize-collecting k-steiner tree(PCkST) *** are given a graph G=(V,E) and an integer *** graph is connected and undirected.A vertex r ∈ V called root and a subset R?V called terminals are also given.A feasible solution for the PCkST is a tree F rooted at r and connecting at least k vertices in *** a vertex from the tree incurs a penalty cost,and including an edge in the tree incurs an edge *** wish to find a feasible solution with minimum total *** total cost of a tree F is the sum of the edge costs of the edges in F and the penalty costs of the vertices not in *** present a simple approximation algorithm with the ratio of 5.9672 for the *** algorithm uses the approximation algorithms for the prize-collecting steiner tree(PCST) problem and the k-steiner tree(kST) problem as *** we propose a primal-dual based approximation algorithm and improve the approximation ratio to 5.

关键词： prize-collecting steiner tree approximation algorithm

A Practical Algorithm for the Minimum Rectilinearsteiner tree

在线全文

学校读者我要写书评

暂无评论

Journal of Computer Science & Technology 2000年第1期15卷 96-99页

作者：马军杨波马绍汉 Department of Computer Science Shandong University Jinan P.R. China

An O(n2) time approximation algorithm for the minimum rectilinear steiner tree is proposed. The approximation ratio of the algorithm is strictlyless than 1.5. The computing performances show the costs of the spanning ... 详细信息

关键词： steiner tree complexity theory combination optimization

Some Results on Spanning trees

在线全文

学校读者我要写书评

暂无评论

Acta Mathematicae Applicatae Sinica 2010年第4期26卷 607-616页

作者： Bing Yao Zhong-fu Zhang Jian-fang Wang College of Mathematics and Information Science Northwest Normal UniversityLanzhou 730070China Academy of Mathematics and Systems Science Chinese Academy of SciencesBeijing 100190China

Some structures of spanning trees with many or less leaves in a connected graph are *** show（1） a connected graph G has a spanning tree T with minimum leaves such that T contains a longest path,and（2） a connected graph G on n vertices contains a spanning tree T with the maximum leaves such that Δ（G） =Δ（T） and the number of leaves of T is not greater than n D（G）＋1,where D（G） is the diameter of G.

关键词： Spanning tree leaves diameter steiner tree independent number

An Efficient Algorithm for Skyline Queries in Cloud Computing Environments

在线全文

学校读者我要写书评

暂无评论

China Communications 2018年第10期15卷 182-193页

作者： Zhenhua Huang Weicheng Xu Jiujun Cheng Juan Ni School of Computer Science South China Normal University Department of Computer Science and Technology Tongji University

Skyline query processing has recently received a lot of attention in database and data mining communities. However, most existing algorithms consider how to efficiently process skyline queries from base tables. Obviously, when the data size and the number of skyline queries increase, the time cost of skyline queries will increase exponentially, which will seriously influence the query efficiency. Motivated by the above, in this paper, we consider improving the query efficiency via skyline views and propose a cost-based algorithm(abbr. CA) to efficiently select the optimal set of skyline views for storage. The CA algorithm mainly includes two phases:(i) reduce the skyline views selection to the minimum steiner tree problem and obtain the approximate optimal set AOS of skyline views, and(ii) adjust AOS and produce the final optimal set FOS of skyline views based on the simulated annealing. Moreover, in order to improve the extendibility of the CA algorithm, we implement it based on the map/reduce distributed computation model in cloud computing environments. The detailed theoretical analyses and extensive experiments demonstrate that the CA algorithm is both efficient and effective.

关键词： skyline query cloud computing steiner tree simulated annealing

Multicast Routing Based on Hybrid Genetic Algorithm

在线全文

学校读者我要写书评

暂无评论

Journal of Beijing Institute of Technology 2005年第2期14卷 130-134页

作者：曹元大蔡刿 School of Software Beijing Institute of Technology Beijing100081 China School

A new multicast routing algorithm based on the hybrid genetic algorithm (HGA) is proposed. The coding pattern based on the number of routing paths is used. A fitness function that is computed easily and makes algorithm quickly convergent is proposed. A new approach that defines the HGA's parameters is provided. The simulation shows that the approach can increase largely the convergent ratio, and the fitting values of the parameters of this algorithm are different from that of the original algorithms. The optimal mutation probability of HGA equals 0.50 in HGA in the experiment, but that equals 0.07 in SGA. It has been concluded that the population size has a significant influence on the HGA's convergent ratio when it's mutation probability is bigger. The algorithm with a small population size has a high average convergent rate. The population size has little influence on HGA with the lower mutation probability.

关键词： multicast routing hybrid genetic algorithm(HGA) simulation algorithm steiner tree

在线全文

学校读者我要写书评

暂无评论

Journal of Donghua University(English Edition) 2014年第2期31卷 128-132页

作者：蔡阿妮宫学庆钱卫宁周傲英 Institute of Massive Computing Software EngineeringEast China Normal University

Research papers are of great importance for researchers to record and share their ideas,studies and results. Meanwhile,they are the bases for further research work. Finding related research papers is the preliminary of good research. A new method for ranking related research papers is introduced in this paper. Given a set of interested papers,the method proposed in this paper may rank related papers just based on a citation graph by constructing the minimal steiner trees. The method can work with the existing keyword based methods. Intensive experiments on a specific research topic show that the proposed method provides a different ranking criterion to existing ones,and can effectively retrieve those highly related papers.

关键词： research paper citation graph steiner tree

Detailed Routing Algorithm with Optical Proximity Effects Constraint

在线全文

学校读者我要写书评

暂无评论

Journal of Semiconductors 2007年第2期28卷 189-195页

作者：周强蔡懿慈张为洪先龙清华大学计算机科学与技术系北京100084

We present a detailed routing algorithm considering the optical proximity effect. The light intensity is calculated beforehand and stored in look-up tables. These costs are used as a constraint to guide the sequential routing. The routing algorithm is based on constructed force directed steiner tree routing to enhance routing efficien- cy. Experimental results on industrial benchmark circuits show that the presented routing algorithm can obtain much improvement considering optical effects short runtime.

关键词： optical proximity effect detailed routing steiner tree yield

在线全文

学校读者我要写书评

暂无评论

基于k-truss的紧密社区查询算法研究

基于k-truss的紧密社区查询算法研究

作者：魏天柱燕山大学

学位级别：硕士

基于k-truss的紧密社区查询问题是根据给定的查询结点集合,返回一个包含所有查询结点且联系最紧密的社区。紧密社区所属的k-truss社区对应k值越大,社区内冗余结点越少,则紧密社区的质量越高,内部结点之间的联系越紧密。本文针对查找基于... 详细信息

基于k-truss的紧密社区查询问题是根据给定的查询结点集合,返回一个包含所有查询结点且联系最紧密的社区。紧密社区所属的k-truss社区对应k值越大,社区内冗余结点越少,则紧密社区的质量越高,内部结点之间的联系越紧密。本文针对查找基于k-truss的高质量紧密社区问题进行研究,具体研究内容如下。首先,通过对现有算法进行分析,发现现有算法在第一阶段查找包含所有查询结点且k值尽可能大的初始k-truss社区时,扩张过程中加入过多无效结点,导致得到的初始k-truss社区k值偏小;在第二阶段删除初始k-truss社区中受“搭便车效应”影响的冗余结点时,现有批量删除策略并不能最大化的去除冗余结点,导致最终得到的紧密社区规模偏大。其次,针对已有算法第一阶段初始k-truss社区k值偏小的问题,提出基于边的steiner tree扩张策略,该策略通过steiner tree中两个邻接结点确定候选结点。与已有扩张策略相比,本文提出的改进策略对加入扩张子图的候选结点要求更为严格,在初始社区规模存在上限的情况下,能够加入更多有效结点,可得到k值更大的初始k-truss社区。再次,针对已有算法第二阶段删除“搭便车效应”结点效果不理想的问题提出了BulkDelete++算法。该算法首先采用批量删除具有最大查询距离的结点策略,当批量删除使当前子图不再满足k-truss社区性质时,停止批量删除操作;然后使用遍历删除当前最大查询距离结点集合的策略,进而可以删除更多冗余结点。最后,基于多组真实数据集进行测试,实验结果从初始k-truss社区质量、扩张操作耗时、紧密社区规模三个方面进行比较,验证了本文提出算法的有效性。

关键词：紧密社区查询 k-truss steiner tree 搭便车效应

Multi-Robot Dispatching in A Geographically Constrained Environment

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

Multi-Robot Dispatching in A Geographically Constrained Envi...