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

AN optimal algorithm FOR FINDING THE MOST VITAL EDGE WITH RESPECT TO SKT RELIABILITY IN BSP DIGRAPHS

JOURNAL OF THE CHINESE INSTITUTE OF ENGINEERS 1995年第4期18卷 519-529页

作者： WANG, PF LEU, SC HSU, LH NATL CHAO TUNG UNIV DEPT INFORMAT SCIHSINCHU 300TAIWAN

The SKT reliability is the probability that a source can send communication to a specified set of terminals K in V in a probabilistic digraph D = (V, E). ''The most vital edge'' is the edge whose deletion yields the largest decrease in the SKT reliability. A digraph is a basically-series-parallel(BSP) directed graph if its underlying undirected graph is series-parallel. In this paper, we propose a tree-like structure and present an optimal algorithm with linear time complexity for finding the most vital edge with respect to SKT reliability in BSP digraphs.

关键词： optimal algorithm BASIC-SERIES-PARALLEL DIGRAPHS MOST VITAL EDGE NETWORK RELIABILITY

来源：评论

学校读者我要写书评

暂无评论

AN optimal algorithm FOR FINDING A MAXIMUM INDEPENDENT SET OF A CIRCULAR-ARC GRAPH: 收藏
分享
引用; SIAM JOURNAL ON COMPUTING 1988年第1期17卷 41-52页; 作者： MASUDA, S NAKAJIMA, K UNIV MARYLAND SYST RES CTR COLLEGE PK MD 20742 USA; A new algorithm is presented for finding a maximum independent set of a circular-arc graph. When the graph is given in the form of a family of n arcs, our algorithm requires only O(n⋅logn)<span style="display:... 详细信息; A new algorithm is presented for finding a maximum independent set of a circular-arc graph. When the graph is given in the form of a family of n arcs, our algorithm requires only $O (n \cdot \log n)$; 来源：评论; 学校读者我要写书评

暂无评论

optimal algorithm for scheduling CBR traffic in ATM switches

引用

ELECTRONICS LETTERS 1999年第13期35卷 1057-1058页

作者： Lee, KK Lee, BS Tan, CW Nanyang Technol Univ Sch Appl Sci Singapore 639798 Singapore

A non-blocking input buffered ATM switch that supports CBR and ABR traffic using a TDM scheduler frame is considered. A new TDM scheduler algorithm (largest-first) for CBR traffic is compared with four others, based on the evenness of the distribution of unused timeslots in the scheduling frame. An even distribution of unused slots minimises the average latency and jitter for ABR traffic. Simulation results show that largest-first allocation is the best.

关键词： constant bit rate TDM scheduler algorithm optimal algorithm electronic switching systems CBR traffic scheduling asynchronous transfer mode Communication switching telecommunication traffic average latency jitter available bit rate TDM scheduler frame scheduling ABR traffic largest-first allocation ATM switches non-blocking input buffered switch Electronic switching systems and exchanges

来源：评论

学校读者我要写书评

暂无评论

An optimal algorithm for certain boundary value problem

引用

JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS 1997年第2期83卷 195-203页

作者： Stys, K Stys, T UNIV BOTSWANA & SWAZILAND DEPT MATHPRIVATE BAG 0022GABORONEBOTSWANA

The O(h(4)) finite-difference scheme for the second derivative u ''(x) leads to a coherent pentadiagonal matrix which is factorized into two tridiagonal matrices. This factorization is used to derive an optimal algorithm for solving a linear system of equations with the pentadiagonal matrix. As an application, a nonlinear system of ordinary differential equations is approximated by an O(h(4)) convergent finite-difference scheme. This scheme is solved by the implicit iterative method applying the algorithm at each iteration. A Mathematica module designed for the purpose of testing and using the method is attached.

关键词： optimal algorithm boundary problem sparse matrices

来源：评论

学校读者我要写书评

暂无评论

optimal algorithm for tree scheduling with unit time communication delays

引用

IEE PROCEEDINGS-COMPUTERS AND DIGITAL TECHNIQUES 2001年第2期148卷 79-88页

作者： Wajdi, T Imtiaz, A Arabian Adv Syst Safat 13035 Kuwait Kuwait Univ Dept Comp Engn Safat 13060 Kuwait

A program is usually designed to act as a set of interacting tasks that can be used to construct a graph. These tasks can be assigned to processing elements in different ways. The scheduling problem is applied to defining an assignment of tasks in order to process elements that will optimise certain performance indices. One of the most important reasons for scheduling indices is to try to optimise the finishing time. The finishing time of a program is the result of two components: the computing time and communication delays. An optimal schedule is defined as the one that assigns tasks to processing elements in such a way as to finish at the earliest possible time. Completion of the optimum solution for arbitrary directed acyclic task graphs (DAGs) has been shown to be NP-complete. However, for some special classes of DAGs (such as fork, join, coarse-grain trees and some fine grain trees) many algorithms have been introduced to find optimal schedules. Note that most of these algorithms do not take into consideration the delays due to message passing among the processors. In the paper, the authors study the increase in time complexity due to communication delays. The particular problem that is addressed is the scheduling problem of the in-forest/out-forest. This paper introduces the first known linear time algorithm for finding the optimal schedule, for the special case of tree-like graphs, with unit time computation and unit time communication delays.

关键词： time complexity Computer networks and techniques directed acyclic task graphs directed graphs processor scheduling message passing NP-complete problem computational complexity optimal algorithm tree scheduling Combinatorial mathematics Computational complexity communication delays delays unit time communication delays Distributed systems software performance indices

来源：评论

学校读者我要写书评

暂无评论

optimal algorithm FOR TESTING STUCK-AT FAULTS IN RANDOM-ACCESS MEMORIES

引用

IEEE TRANSACTIONS ON COMPUTERS 1977年第11期26卷 1141-1144页

作者： KNAIZUK, J HARTMANN, CRP SUNY COLL OSWEGO DEPT COMP SCIOSWEGONY 13126 SYRACUSE UNIV SCH COMP & INFORMAT SCISYRACUSENY 13210

This correspondence presents an optimal algorithm to detect any single "stuck-at-i," "stuck-at-O" fault and any combination of "stuck-at-I," "stuck-at-O" multiple faults in a ra... 详细信息

This correspondence presents an optimal algorithm to detect any single "stuck-at-i," "stuck-at-O" fault and any combination of "stuck-at-I," "stuck-at-O" multiple faults in a random access memory using only the n-bit memory address register input and m-bit memory buffer register input and output lines. It is shown that this algorithm requires 4 X 2n memory accesses.

关键词： Fault Detection Stuck At Aults optimal algorithm Random Access Memories

来源：评论

学校读者我要写书评

暂无评论

An optimal algorithm for computing the non-trivial circuits of a union of iso-oriented rectangles

引用

INFORMATION PROCESSING LETTERS 2013年第3期113卷 55-59页

作者： Alevizos, Panagiotis D. Univ Patras Dept Math GR-26500 Patras Greece

Given n rectangles R-1, ..., R-n on the plane with sides parallel to the coordinate axes, Lipski and Preparata (1981) [1] have presented a Theta(n log n) time and O(n log n) space algorithm for computing the non-trivial circuits of the union u = R-1 boolean OR ... boolean OR R-n. In this paper, we are presenting a simple algorithm, which computes the non-trivial circuits of u in Theta(n log n) time and Theta(n) space. (C) 2012 Elsevier B.V. All rights reserved.

关键词： Computational geometry Circuit Contour Rectilinear polygons optimal algorithm Sweep plane

来源：评论

学校读者我要写书评

暂无评论

An optimal algorithm for two robots path planning problem on the grid

引用

ROBOTICS AND AUTONOMOUS SYSTEMS 2013年第12期61卷 1406-1414页

作者： Davoodi, Mansoor Abedin, Marjan Banyassady, Bahareh Khanteimouri, Payam Mohades, Ali Inst Adv Studies Basic Sci Dept Comp Sci & Informat Technol Zanjan Iran Amirkabir Univ Technol Dept Math & Comp Sci Lab Algorithms & Computat Geometry Tehran Iran

This paper is a study on the problem of path planning for two robots on a grid. We consider the objective of minimizing the maximum path length which corresponds to minimizing the arrival time of the last robot at its goal position. We propose an optimal algorithm that solves the problem in linear time with respect to the size of the grid. We show that the algorithm is complete;meaning that it is sure to find an optimal solution or report if any does not exist. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Multi-robot path planning Min-Max problem Grid optimal algorithm

来源：评论

学校读者我要写书评

暂无评论

OptDynLim: An optimal algorithm for the One-Dimensional RSU Deployment Problem With Nonuniform Profit Density

引用

IEEE TRANSACTIONS ON INDUSTRIAL INFORMATICS 2019年第2期15卷 1052-1061页

作者： Gao, Zhenguo Chen, Danjie Cai, Shaobin Wu, Hsiao-Chun Huaqiao Univ Coll Comp Sci & Technol Xiamen 361021 Peoples R China Huaqiao Univ Coll Civil Engn Xiamen 361021 Peoples R China Louisiana State Univ Sch Elect Engn & Comp Sci Baton Rouge LA 70803 USA

Proper deployment of roadside units (RSUs) is of crucial importance to vehicular ad hoc networks (VANETs). However, our understandings to the simple one-dimensional RSU Deployment (D1RD) problem with nonuniform profit density is still seriously limited. In this paper, we analyze the D1RD problem and try to design optimal algorithms for it. We first analyze the properties of the optimal solutions of the D1RD problem involving a single RSU, and then extend to multiple RSUs. Next, we propose an efficient technique named Dynamic Limiting (DynLim), which reduces the solution search space size considerably by adjusting search space limits dynamically. Finally, an optimal algorithm named OptDynLim is proposed based on the DynLim technique, and its optimality is proved. Numerical simulations validate the correctness of our analyzes and show that DynLim can usually reduce solution search space size by more than 99%.

关键词： Dynamic limiting (DynLim) technique nonuniform profit density one-dimensional RSU deployment (D1RD) problem optimal algorithm VANETs

来源：评论

学校读者我要写书评

暂无评论

An optimal algorithm for one-separation of a set of isothetic polygons

引用

INFORMATION SCIENCES 2004年第1-4期164卷 65-88页

作者： Datta, A Krithivasan, K Ottmann, T Univ Western Australia Sch Comp Sci & Software Engn Perth WA 6009 Australia Indian Inst Technol Dept Comp Sci & Engn Madras 600036 Tamil Nadu India Univ Freiburg Inst Informat D-79110 Freiburg Germany

We consider the problem of separating a collection of isothetic polygons in the plane by translating one polygon at a time to infinity. The directions of translation are the four isothetic (parallel to the axes) directions, but a particular polygon can be translated only in one of these four directions. Our algorithm detects whether a scene is separable in this sense and computes a translational ordering of the polygons. The time and space complexities of our algorithm are O(n log n) and O(n) respectively, where n is the total number of vertices of the polygons in the scene. The best previous algorithm in the plane for this problem has complexities of O(n log(2) n) time and O(n log n) space. (C) 2003 Elsevier Inc. All rights reserved.

关键词： isothetic polygons one-separation motion planning computational geometry optimal algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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