检索结果-内蒙古大学图书馆

optimal-algorithmS FOR TOTAL EXCHANGE WITHOUT BUFFERING ON THE HYPERCUBE

BIT 1992年第4期32卷 559-569页

作者： COOLSAET, K DEMEYER, H FACK, V STATE UNIV GHENT SEMINARIE ALGEBRA & FUNCT ANALB-9000 GHENTBELGIUM STATE UNIV GHENT NUMER WISKUNDE & INFORMAT LABB-9000 GHENTBELGIUM

Two methods are given for constructing total exchange algorithms for hypercubic processor networks. This is done by means of bit sequences with special properties. The algorithms are optimal with respect to a given time model, need no intermediate message buffering and are local in the sense that every processor executes basically the same program.

关键词： HYPERCUBE TOTAL EXCHANGE optimal algorithm

来源：评论

学校读者我要写书评

暂无评论

An optimal EREW PRAM algorithm for minimum spanning tree verification

引用

INFORMATION PROCESSING LETTERS 1997年第3期62卷 153-159页

作者： King, V Poon, CK Ramachandran, V Sinha, S UNIV TEXAS DEPT COMP SCIAUSTINTX 78712 UNIV VICTORIA DEPT COMP SCIVICTORIABCCANADA

We present a deterministic parallel algorithm on the EREW PRAM model to verify a minimum spanning tree of a graph. The algorithm runs on a graph with n vertices and m edges in O(log n) time and O(m + n) work. The algorithm is a parallelization of King's Linear time sequential algorithm for the problem. (C) 1997 Elsevier Science B.V.

关键词： parallel algorithms minimum spanning tree verification EREW PRAM design of algorithms optimal algorithm

来源：评论

学校读者我要写书评

暂无评论

optimal algorithms for recombination distance problem

Optimal algorithms for recombination distance problem

引用

1st International Conference on Optimization Methods and Software (OMS2002)

作者： He, Y Chen, T Zhejiang Univ Dept Math Hangzhou 310027 Peoples R China Zhejiang Univ State Key Lab CAD & CG Hangzhou 310027 Peoples R China

Recombination of sequences is an important combinatorial optimization problem due to its applications in computational biology. It is related to the alignment with recombination which is an edit distance problem involved recombination, and reconstructing a history of recombination from a set of sequences, etc. Recently, Wu and Gu discussed a distance problem involved recombination consisting of single crossover. [S. Wu and X. Gu (2001). A Greedy algorithm for optimal recombination. Proceeding of COCOON2001, Lecture Notes in Computer Science 2108 , pp. 86-90.] A and S denote two collections of sequences where \S\ = 2. The goal is to generate A from S by a series of recombinations in minimum number of steps. They defined a special class A of sequences called 'tree', and presented a greedy algorithm which was claimed optimal for finding the recombination distance from S to A. In this paper, we revisit this result. We show that the greedy algorithm is not always optimal, and propose a revised algorithm which can solve the problem optimally. We further propose a new class A of sequences called 'chain' and provide a polynomial time algorithm for finding the optimal recombination evolutionary history from S to A.

关键词： recombination of sequences computational biology optimal algorithm tree chain

来源：评论

学校读者我要写书评

暂无评论

An optimal certificate dispersal algorithm for mobile ad hoc networks

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 2005年第5期E88A卷 1258-1266页

作者： Zheng, H Omura, S Uchida, J Wada, K Nagoya Inst Technol Grad Sch Engn Dept Comp Sci & Engn Nagoya Aichi 4668555 Japan

In this paper, we focus on the problem that in an ad hoc network, how to send a message securely between two users using the certificate dispersal system. In this system, special data called certificate is issued between two users and these issued certificates are stored among the network. Our final purpose on this certificate dispersal problem is to construct certificate graphs with lower dispersability cost which indicates the average number of certificates stored in each node in an ad hoc network. As our first step, when a certificate graph is given, we construct two efficient certificate dispersal algorithms for strongly connected graphs and directed graphs in this paper. We can show that for a strongly connected graph G = (V, E) and a directed graph H = (V', E'), new upper bounds on dispersability cost on the average number of certificates stored in one node are O(D-G + vertical bar E vertical bar/vertical bar V vertical bar) and O(p(G)d(max) + vertical bar E'vertical bar/vertical bar V'vertical bar) respectively, where D-G is the diameter of G, d(max) is the maximum diameter of strongly connected components of H and PG is the number of strongly connected components of H. Furthermore, we give some new lower bounds for the problem and we also show that our algorithms are optimal for several graph classes.

关键词： Certificate dispersability Certificate dispersal algorithm Mobile ad hoc network optimal algorithm

来源：评论

学校读者我要写书评

暂无评论

Privacy-aware trajectory data publishing: an optimal efficient generalisation algorithm

引用

INTERNATIONAL JOURNAL OF GRID AND UTILITY COMPUTING 2023年第6期14卷 632-643页

作者： Harnsamut, Nattapon Natwichai, Juggapong Chiang Mai Univ Fac Engn Comp Engn Dept Data Engn Lab Chiang Mai Thailand Chiang Mai Univ Fac Engn Data Engn Lab Dept Comp Engn Chiang Mai Thailand Chiang Mai Univ Ctr Data Analyt & Knowledge Synth Healthcare Chiang Mai Thailand

With the increasing location-aware technologies that provide positioning services, it is easy to collect users' trajectory data. Such data could often contain sensitive information, i.e., private locations, private trajectory or path, and other sensitive attributes. In this paper, we propose a privacy preservation algorithm based on LKC-privacy model to protect the privacy attacks of trajectory data publishing. Not only can the data utility be maintained effectively by the data generalisation approach, but this algorithm can also reduce the computing time of the look-up table creation which is one of the highest computational processes. Our proposed algorithm is evaluated with extensive experiments. From the experiments, the enhanced-LT algorithm performance in terms of the execution time outperforms the baseline LT algorithm by 48.5% on average. The results show that our proposed algorithm returns not only the optimal solution but also highly efficient computation times.

关键词： LKC-privacy trajectory data publishing optimal algorithm generalisation technique

来源：评论

学校读者我要写书评

暂无评论

optimal algorithms for the Economic Lot-Sizing Problem with Multi-supplier

Optimal Algorithms for the Economic Lot-Sizing Problem with ...

引用

6th International Conference on algorithmic Aspects in Information and Management

作者： Bai, Qing-Guo Xu, Jian-Teng Qufu Normal Univ Sch Operat Res & Management Sci Rizhao 276826 Shandong Peoples R China Sch Management Harbin Inst Technol Harbin Peoples R China

ISBN: (纸本)9783642143540

This paper considers the economic lot-sizing problem with multi-supplier in which the retailer may replenish his inventory from several suppliers. Each supplier is characterized by one of two types of order cost structures: incremental quantity discount cost structure and multiple set-ups cost structure. The problem is challenging clue to the mix of different cost structures. By analyzing the optimal properties, we reduce the searching range of the optimal solutions and develop several optimal algorithms to solve all cases of this multi-supplier problem.

关键词： Economic lot-sizing optimal algorithm dynamic programming

来源：评论

学校读者我要写书评

暂无评论

An optimal real time algorithm for determine the convex hull of a set of points in a plane

引用

COMPUTERS & INDUSTRIAL ENGINEERING 1998年第1-2期35卷 331-334页

作者： Wang, ZQ Xiao, LJ Shanghai Jiao Tong Univ Dept Engn Mech Shanghai 200240 Peoples R China

Based on the properties of star polygon and that the convex polygon is a special kind of star polygon, with the star point as the origin and the two lines respectively parallel to the x-axis and y-axis as coordinate axis, a relative coordinate system is built and the planar area is divided into four areas. Based on the new equation of relationship of point to orientation line, inner points and externals point of polygon are quickly separated, the embraced vertices (tangent vertices) of external points are rapidly found. An optimal real time algorithm for constructing the convex hull of a set of points in a plane is proposed. (C) 1998 Elsevier Science Ltd. All rights reserved.

关键词： convex hull set of points star polygon optimal algorithm real time processing

来源：评论

学校读者我要写书评

暂无评论

optimal and suboptimal algorithms in set membership identification

引用

MATHEMATICAL AND COMPUTER MODELLING OF DYNAMICAL SYSTEMS 2005年第2期11卷 159-169页

作者： Kacewicz, B AGH Univ Sci & Technol Dept Appl Math PL-30059 Krakow Poland

We discuss in this paper optimality properties of identification algorithms in a set membership framework. We deal with restricted-complexity (conditional) identification, where approximations (models) to a possibly complex system are selected from a low dimensional space. We discuss the worst- and average-case settings. In the worst-case setting, we present results on optimality, or suboptimality, of algorithms based on computing the unconditional or conditional Chebyshev centres of an uncertainty set. In the average-case setting, we show that the optimal algorithm is given by the projection of the unconditional Chebyshev centre. We show explicit formulas for its average errors, allowing us to see the contribution of all problem parameters to the minimal error. We discuss the case of weighted average errors corresponding to non-uniform distributions over uncertainty sets, and show how the weights influence the minimal identification error.

关键词： identification worst-case setting average-case setting weights optimal algorithm suboptimal algorithm

来源：评论

学校读者我要写书评

暂无评论

optimal PARALLEL 3-COLORING algorithm FOR ROOTED TREES AND ITS APPLICATIONS

引用

INFORMATION PROCESSING LETTERS 1992年第3期41卷 153-156页

作者： RAJCANI, P Department of Computer Science University of South Carolina Columbia SC 29208 USA

An optimal O(DELTA-log n/log n) parallel algorithm for 3-coloring of rooted trees with maximum degree-DELTA that uses n log log n/log n processors on a CRCW PRAM is presented. This algorithm is used in the design of optimal parallel algorithms for 7-coloring of planar graphs, finding a maximal independent set and a maximal matching in planar graphs.

关键词： PARALLEL algorithmS GRAPH COLORING ROOTED TREES PLANAR GRAPHS optimal algorithm

来源：评论

学校读者我要写书评

暂无评论

Efficient and optimal algorithms for Tree Summarization With Weighted Terminologies

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2023年第3期35卷 2500-2514页

作者： Zhu, Xuliang Huang, Xin Choi, Byron Xu, Jianliang Cheung, William K. Zhang, Yanchun Liu, Jiming Hong Kong Baptist Univ Dept Comp Sci Hong Kong Peoples R China Guangzhou Univ Guangzhou 510006 Peoples R China Victoria Univ Footscray Vic 3011 Australia

Data summarization that presents a small subset of a dataset to users has been widely applied in numerous applications and systems. Many datasets are coded with hierarchical terminologies, e.g., gene ontology, disease ontology, to name a few. In this paper, we study the weighted tree summarization. We motivate and formulate our kWTS-problem as selecting a diverse set of k nodes to summarize a hierarchical tree T with weighted terminologies. We first propose an efficient greedy tree summarization algorithm GTS. It solves the problem with (1 -1/e)-approximation guarantee. Although GTS achieves quality-guaranteed answers approximately, but it is still not optimal. To tackle the problem optimally, we further develop a dynamic programming algorithm OTS to obtain optimal answers for kWTS-problem in O(nhk(3)) time, where n, h are the node size and height in tree T. The algorithm complexity and correctness of OTS are theoretically analyzed. In addition, we propose a useful optimization technique of tree reduction to remove useless nodes with zero weights and shrink the tree into a smaller one, which ensures the efficiency acceleration of both GTS and OTS in real-world datasets. Moreover, we illustrate one useful application of graph visualization based on the answer of k-sized tree summarization and show it in a novel case study. Extensive experimental results on real-world datasets show the effectiveness and efficiency of our proposed approximate and optimal algorithms for tree summarization. Furthermore, we conduct a usability evaluation of attractive topic recommendation on ACM Computing Classification System dataset to validate the usefulness of our model and algorithms.

关键词： Diseases Heuristic algorithms Terminology Approximation algorithms Ontologies Dynamic programming Optimization Hierarchy tree data summarization optimal algorithm top-k

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：