检索结果-南通市图书馆

A Two-Player Coalition Cooperative Scheme for the Bodyguard Allocation Problem

维普期刊数据库

同方期刊数据库评论

在线全文

学校读者我要写书评

暂无评论

Journal of Computer Science & Technology 2018年第4期33卷 823-837页

作者： Jose Alberto Fernandez-Zepedu Daniel Brubeck-Salcedo Daniel Fajardo-Delgado Hector Zatarain-Aceves Department of Computer Science Center for Scientific Research and Higher Education of Ensenada Ensenada BC 22860 Mexico Department of Systems and Computation Instituto Technol6gico de Ciudad Guzmdn Guzmdn JAL 49100 Mexico

We address the bodyguard allocation problem （BAP）, an optimization problem that illustrates the conflict of interest between two classes of processes with contradictory preferences within a distributed system. While a class of processes prefers to minimize its distance to a particular process called the root, the other class prefers to maximize it; at the same time, all the processes seek to build a communication spanning tree with the maximum social welfare. The two state-of-the-art algorithms for this problem always guarantee the generation of a spanning tree that satisfies a condition of Nash equilibrium in the system; however, such a tree does not necessarily produce the maximum social welfare. In this paper, we propose a two-player coalition cooperative scheme for BAP, which allows some processes to perturb or break a Nash equilibrium to find another one with a better social welfare. By using this cooperative scheme, we propose a new algorithm called FFC-BAPs for BAP. We present both theoretical and empirical analyses which show that this algorithm produces better quality approximate solutions than former algorithms for BAP.

关键词： bodyguard allocation problem coalitional game graph algorithm Nash equilibrium

Efficient Minimum Spanning Tree algorithms on the Reconfigurable Mesh

在线全文

维普期刊数据库

学校读者我要写书评

暂无评论

Journal of Computer Science & Technology 2000年第2期15卷 116-125页

作者：万颖瑜许胤龙顾晓东陈国良 Department of Computer Science and Technology University of Science and Technology of China National High Performance Computation Center at Hefei Hefei P.R. China

The reconfigurable mesh consists of an array of processors interconnected by a reconfigurable bus system. The bus system can be used to dynamically obtain various interconnection patterns among the processors. Recently, this model has attracted a lot of attention. In this paper, two efficient algorithms are proposed for computing the minimum spanning tree of an n-vertex undirected graph. One runs on an n×n reconfigurable mesh with time complexity of O(log^2 n). The other runs with time complexity of O(log n) on an n^(1+E)×n reconfigurable mesh, where < E < 1 is a constant. All these improve the previously known results on the reconfigurable mesh.

关键词： parallel algorithm reconfigurable mesh graph algorithm minimum spanning tree

Automatic Multi-Document Summarization Based on Keyword Density and Sentence-Word graphs

维普期刊数据库

同方期刊数据库评论

在线全文

学校读者我要写书评

暂无评论

Journal of Shanghai Jiaotong university(Science) 2018年第4期23卷 584-592页

作者： YE Feiyue XU Xinchen School of Computer Engineering and Science Shanghai UniversityShanghai 200444China

As a fundamental and effective tool for document understanding and organization, multi-document summarization enables better information services by creating concise and informative reports for large collections of documents. In this paper, we propose a sentence-word two layer graph algorithm combining with keyword density to generate the multi-document summarization, known as graph ＆ Keywordp. The traditional graph methods of multi-document summarization only consider the influence of sentence and word in all documents rather than individual documents. Therefore, we construct multiple word graph and extract right keywords in each document to modify the sentence graph and to improve the significance and richness of the summary. Meanwhile, because of the differences in the words importance in documents, we propose to use keyword density for the summaries to provide rich content while using a small number of words. The experiment results show that the graph ＆ Keywordp method outperforms the state of the art systems when tested on the Duc2004 data set. Key words： multi-document, graph algorithm, keyword density, graph ＆ Keywordp, Due2004

关键词： multi-document graph algorithm keyword density graph & Keywordρ Duc2004

Approximation algorithms for Steiner Connected Dominating Set

维普期刊数据库

同方期刊数据库评论

在线全文

学校读者我要写书评

暂无评论

Journal of Computer Science & Technology 2005年第5期20卷 713-716页

作者： Ya-Feng Wu Yin-Long Xu Guo-Liang Chen National High Performance Computing Center at Hefei Department of Computer Science and Technology University of Science and Technology of China Hefei 230027 P.R. China

Steiner connected dominating set （SCDS） is a generalization of the famous connected dominating set problem, where only a specified set of required vertices has to be dominated by a connected dominating set, and known to be NP- hard. This paper firstly modifies the SCDS algorithm of Guha and Khuller and achieves a worst case approximation ratio of （2 ＋ 1/（m - 1））H（min（△, k））＋O（1）, which outperforms the previous best result （c ＋ 1）H（min（△, k））＋ O（1） in the case of m ≥ 1 ＋1/（c - 1）, where c is the best approximation ratio for Steiner tree, A is the maximum degree of the graph, k is the cardinality of the set of required vertices, m is an optional integer satisfying 0 ≤ m ≤ min（△, k） and H is the harmonic function. This paper also proposes another approximation algorithm which is based on a greedy approach. The second algorithm can establish a worst case approximation ratio of 2 ln（min（△, k））＋ O（1）, which can also be improved to 2 lnk if the optimal solution is greater than c·e^2c＋1/2（c＋1）.

关键词： approximation algorithm Steiner connected dominated set graph algorithm NP-hard

PRIME： A Mass Spectrum Data Mining Tool for De Novo Sequencing and PTMs Identification

在线全文

维普期刊数据库

学校读者我要写书评

暂无评论

Journal of Computer Science & Technology 2005年第4期20卷 483-490页

作者：严波瞿幼星毛凤楼欧胜利徐鹰 ComputationalSystemsBiologyLaboratory DepartmentofBiochemicalandMolecularBiologyUniversityofGeorgiaAthensGA30602U.S.A. ComputationalSystemsBiologyLaboratory DepartmentofBiochemicalandMolecularBiologyUniversityofGeorgiaAthensGA30602U.S.A.／／ComputationalBiologyInstituteOakRidgeNationalLaboratoryOakRidgeTN37831U.S.A.

De novo sequencing is one of the most promising proteomics techniques for identification of protein posttranslation modifications (PTMs) in studying protein regulations and functions. We have developed a computer tool PRIME for identification of b and y ions in tandem mass spectra, a key challenging problem in de novo sequencing. PRIME utilizes a feature that ions of the same and different types follow different mass-difference distributions to separate b from y ions correctly. We have formulated the problem as a graph partition problem. A linear integer-programming algorithm has been implemented to solve the graph partition problem rigorously and efficiently. The performance of PRIME has been demonstrated on a large amount of simulated tandem mass spectra derived from Yeast genome and its power of detecting PTMs has been tested on 216 simulated phosphopeptides.

关键词： de novo sequencing graph algorithm protein post-translationalmodifications proteomics tandem mass spectrometry

Near-Optimal Placement of Secrets in graphs

在线全文

维普期刊数据库

学校读者我要写书评

暂无评论

Open Journal of Discrete Mathematics 2016年第4期6卷 238-247页

作者： Werner Poguntke Fachbereich Technische Betriebwirtschaft Fachhochschule Südwestfalen Hagen Germany

We consider the reconstruction of shared secrets in communication networks, which are modelled by graphs whose components are subject to possible failure. The reconstruction probability can be approximated using minimal cuts, if the failure probabilities of vertices and edges are close to zero. As the main contribution of this paper, node separators are used to design a heuristic for the near-optimal placement of secrets sets on the vertices of the graph.

关键词： graph algorithm Cut Secret Sharing Approximation Network Design