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

Incremental Cycle Detection, Topological Ordering, and Strong Component Maintenance

ACM TRANSACTIONS ON algorithms 2012年第1期8卷 3-3页

作者： Haeupler, Bernhard Kavitha, Telikepalli Mathew, Rogers Sen, Siddhartha Tarjan, Robert E. MIT CSAIL Cambridge MA 02139 USA Tata Inst Fundamental Res Mumbai 400005 Maharashtra India Indian Inst Sci Bangalore 560012 Karnataka India Princeton Univ Dept Comp Sci Princeton NJ 08540 USA HP Labs Palo Alto CA 94304 USA

We present two online algorithms for maintaining a topological order of a directed n-vertex acyclic graph as arcs are added, and detecting a cycle when one is created. Our first algorithm handles m arc additions in O(m(3/2)) time. For sparse graphs (m/n = O(1)), this bound improves the best previous bound by a logarithmic factor, and is tight to within a constant factor among algorithms satisfying a natural locality property. Our second algorithm handles an arbitrary sequence of arc additions in O(n(5/2)) time. For sufficiently dense graphs, this bound improves the best previous bound by a polynomial factor. Our bound may be far from tight: we show that the algorithm can take Omega(n(2)2 root(2lgn)) time by relating its performance to a generalization of the k-levels problem of combinatorial geometry. A completely different algorithm running in Theta (n(2) log n) time was given recently by Bender, Fineman, and Gilbert. We extend both of our algorithms to the maintenance of strong components, without affecting the asymptotic time bounds.

关键词： dynamic algorithms directed graphs topological order cycle detection strong components halving intersection arrangement

来源：评论

学校读者我要写书评

暂无评论

On dynamic Shortest Paths Problems

引用

ALGORITHMICA 2011年第2期61卷 389-401页

作者： Roditty, Liam Zwick, Uri Bar Ilan Univ Dept Comp Sci IL-52900 Ramat Gan Israel Tel Aviv Univ Sch Comp Sci IL-69978 Tel Aviv Israel

We obtain the following results related to dynamic versions of the shortest-paths problem: (i) Reductions that show that the incremental and decremental single-source shortest-paths problems, for weighted directed or undirected graphs, are, in a strong sense, at least as hard as the static all-pairs shortest-paths problem. We also obtain slightly weaker results for the corresponding unweighted problems. (ii) A randomized fully-dynamic algorithm for the all-pairs shortest-paths problem in directed unweighted graphs with an amortized update time of (O) over tilde (m root n) (we use (O) over tilde to hide small poly-logarithmic factors) and a worst case query time is O(n(3/4)). (iii) A deterministic O(n(2)log n) time algorithm for constructing an O(log n)-spanner with O(n) edges for any weighted undirected graph on n vertices. The algorithm uses a simple algorithm for incrementally maintaining single-source shortest-paths tree up to a given distance.

关键词： dynamic algorithms Graph Shortest paths Spanners

来源：评论

学校读者我要写书评

暂无评论

Fast dynamic Algorithm for Sequence Alignment Based on Bioinformatics algorithms

Fast Dynamic Algorithm for Sequence Alignment Based on Bioin...

引用

2011 IEEE International Conference on Intelligent Computing and Intelligent Systems(ICIS 2011)

作者： Sara Shehab Hany Mahgoub Arabi Keshk Waiel Fathi Computer Science Dept.Faculty of Computers&Info. Menoufia Univ.Shebin El-KomEgypt Operation Research Dept.Faculty of Computers&Info. Menoufia Univ.Shebin El-KomEgypt

This paper presents a new algorithm for DNA sequence alignment based on concepts from bioinformatics dynamic *** algorithm is called Fast dynamic Algorithm for Sequence Alignment (FDASA).The bioinformatics dynamic algorithms are used for computing the optimal alignment for the sequences,but the problem is these algorithms compute the unused data,this computation take more spaces in memory and decrease the *** new algorithm is proposed for overcoming the problems of dynamic algorithms;the memory spaces and *** experiments are applied on a collection of DNA sequences to compare the new algorithm’s results with the dynamic algorithms *** performance of proposed algorithm is compared with the previous dynamic algorithms for the execution time and memory *** results show that the new algorithm alignment between DNA sequences speed the performance and decrease the memory spaces used than that in the dynamic algorithms alignment for the same DNA ***,the execution time of proposed algorithm is much better than the previous dynamic algorithms.

关键词： FDAS Bioinformatics DNA Sequence alignment dynamic algorithms

来源：评论

学校读者我要写书评

暂无评论

Control of Multi-Hop Communication Networks for Inter-Session Network Coding

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2011年第2期57卷 1092-1110页

作者： Eryilmaz, Atilla Lun, Desmond S. Swapna, B. T. Ohio State Univ Dept Elect & Comp Engn Columbus OH 43210 USA Rutgers State Univ Dept Comp Sci Camden NJ 08102 USA Rutgers State Univ Ctr Comp & Integrat Biol Camden NJ 08102 USA

This paper provides a solution to the question of how, when and where to perform inter-session network coding for a general network model both under wired and wireless conditions. In particular, an original queuing architecture and a dynamic routing-scheduling-coding strategy are introduced for serving multiple sessions when linear network coding is allowed across sessions. This policy provides a novel extension to the class of back-pressure policies by incorporating inter-session coding decisions via simple rules on the relevant queue-length levels. Despite the fact that the capacity region of inter-session coding is a challenging open problem, in this paper, we prove that our algorithm can support any set of rates in a nontrivial characterized region of achievable rates. In addition to its practical implications, this work also provides a theoretical framework in which the gains of inter-session network coding and pure routing can be compared.

关键词： Backpressure policies butterfly network dynamic algorithms inter-session network coding Lyapunov stability stochastic networks

来源：评论

学校读者我要写书评

暂无评论

Partially dynamic algorithms for Distributed Shortest Paths and their Experimental Evaluation

引用

JOURNAL OF COMPUTERS 2007年第9期2卷 16-26页

作者： Cicerone, Serafino D'Angelo, Gianlorenzo Di Stefano, Gabriele Frigioni, Daniele Petricola, Alberto Univ Aquila Dipartimento Ingn Elettr & Informaz I-67040 Laquila Italy

In this paper, we study the dynamic version of the distributed all-pairs shortest paths problem. Most of the solutions given in the literature for this problem, either (i) work under the assumption that before dealing with an edge operation, the algorithm for the previous operation has to be terminated, that is, they are not able to update shortest paths concurrently, or (ii) concurrently update shortest paths, but their convergence can be very slow (possibly infinite). In this paper we propose a partially dynamic algorithm that overcomes most of these limitations. In particular, it is able to concurrently update shortest paths and in many cases its convergence is quite fast. These properties are highlighted by an experimental study whose aim is to show the effectiveness of the proposed algorithms also in the practical case.

关键词： Distributed networks dynamic algorithms shortest paths routing experimental evaluation network simulation environment

来源：评论

学校读者我要写书评

暂无评论

Fast dynamic Transitive Closure with Lookahead

引用

ALGORITHMICA 2010年第2期56卷 180-197页

作者： Sankowski, Piotr Mucha, Marcin Warsaw Univ Inst Informat PL-02097 Warsaw Poland

In this paper we consider the problem of dynamic transitive closure with lookahead. We present a randomized one-sided error algorithm with updates and queries in O(n(omega(1,1,epsilon)-epsilon)) time given a lookahead of n(epsilon) operations, where omega(1,1,epsilon) is the exponent of multiplication of n x n matrix by n x n(epsilon) matrix. For epsilon <= 0.294 we obtain an algorithm with queries and updates in O(n(2-epsilon)) time, whereas for epsilon = 1 the time is O(n(omega-1)). This is essentially optimal as it implies an O(n(omega)) algorithm for boolean matrix multiplication. We also consider the offline transitive closure in planar graphs. For this problem, we show an algorithm that requires O(n(omega/2)) time to process n(1/2) operations. We also show a modification of these algorithms that gives faster amortized queries. Finally, we give faster algorithms for restricted type of updates, so called element updates. All of the presented algorithms are randomized with one-sided error. All our algorithms are based on dynamic algorithms with lookahead for matrix inverse, which are of independent interest.

关键词： Transitive closure dynamic algorithms Lookahead Algebraic algorithms Matrix inverse Planar graphs

来源：评论

学校读者我要写书评

暂无评论

Fully dynamic Algorithm for Recognition and Modular Decomposition of Permutation Graphs

引用

ALGORITHMICA 2010年第2期58卷 405-432页

作者： Crespelle, Christophe Paul, Christophe Univ Montpellier 2 LIRMM Montpellier France LIRMM CNRS Montpellier France

This paper considers the problem of maintaining a compact representation (O(n) space) of permutation graphs under vertex and edge modifications (insertion or deletion). That representation allows us to answer adjacency queries in O(1) time. The approach is based on a fully dynamic modular decomposition algorithm for permutation graphs that works in O(n) time per edge and vertex modification. We thereby obtain a fully dynamic algorithm for the recognition of permutation graphs.

关键词： dynamic algorithms Permutation graphs Modular decomposition

来源：评论

学校读者我要写书评

暂无评论

dynamic multi-dimensional bin packing

引用

JOURNAL OF DISCRETE algorithms 2010年第4期8卷 356-372页

作者： Epstein, Leah Levy, Meital Univ Haifa Dept Math IL-31905 Haifa Israel Tel Aviv Univ Sch Comp Sci Tel Aviv Israel

A natural generalization of the classical online bin packing problem is the dynamic bin packing problem introduced by Coffman et al. (1983) [7]. In this formulation, items arrive and depart and the objective is to minimize the maximal number of bins ever used over all times. We study the oriented multi-dimensional dynamic bin packing problem for two dimensions, three dimensions and multiple dimensions. Specifically, we consider dynamic packing of squares and rectangles into unit squares and dynamic packing of three-dimensional cubes and boxes into unit cubes. We also study dynamic d-dimensional hypercube and hyperbox packing. For dynamic d-dimensional box packing we define and analyze the algorithm NFDH for the offline problem and present a dynamic version. This algorithm was studied before for rectangle packing and for square packing and was generalized only for multi-dimensional cubes. We present upper and lower bounds for each of these cases. (C) 2010 Elsevier B. V. All rights reserved.

关键词： Bin packing Online algorithms dynamic algorithms Multi-dimensional packing

来源：评论

学校读者我要写书评

暂无评论

Ensemble-based methods for describing protein dynamics

引用

CURRENT OPINION IN PHARMACOLOGY 2010年第6期10卷 760-769页

作者： Jacobs, Donald J. Univ N Carolina Dept Phys & Opt Sci Charlotte NC 28223 USA

Molecular dynamics (MD) simulation is a natural approach for studying protein dynamics, and coupled with the ideas of multiscale modeling, MD proves to be the gold standard in computational biology to investigate mechanistic details related to protein function In principle if MD trajectories are long enough, the ensemble of protein conformations generated allows thermodynamic and kinetic properties to be predicted We know from experiments that proteins exhibit a high degree of fidelity in function and that empirical kinetic models are successful in describing kinetics suggesting that the ensemble of conformations cluster into well-defined thermodynamic states, which are frequently metastable The experimental evidence suggest that more efficient computational models that retain only essential properties of the protein can be constructed to faithfully reproduce the relatively few observed thermodynamic states, and perhaps describe transition states if the model is sufficiently detailed Indeed, there are many so-called ensemble-based methods that attempt to generate more complete ensembles than MD can provide by focusing on the most important driving forces through simplified representations of how elements within the protein interact Although coarse-graining is employed in MD and other approaches, such as in elastic network models, the key distinguishing factor of ensemble-based methods is that they are meant to efficiently generate a large ensemble of conformations without solving explicit equations of motion This review highlights three types of ensemble-based methods illustrated by COREX and the Wako-Saito-Munoz-Eaton (WSME) model the Framework Rigidity Optimized dynamic Algorithm (FRODA) and the distance constraint model (DCM)

关键词： Protein Conformation Computational Biology protein structure function Ensembles Thermodynamics Kinetics Equations of motion dynamic algorithms Protein DRIVING FORCE Bioinformatics

来源：评论

学校读者我要写书评

暂无评论

A Faster Algorithm for Computing the Girth of Planar and Bounded Genus Graphs

引用

ACM TRANSACTIONS ON algorithms 2010年第1期7卷 3-3页

作者： Djidjev, Hristo N. Los Alamos Natl Lab Los Alamos NM 87545 USA

The girth of a graph G is the length of a shortest cycle of G. In this article we design an O(n(5/4) log n) algorithm for finding the girth of an undirected n-vertex planar graph, the first o(n(2)) algorithm for this problem. We also extend our results for the class of graphs embedded into an orientable surface of small genus. Our approach uses several techniques such as graph partitioning, hammock decomposition, graph covering, and dynamic shortest-path computation. We discuss extensions and generalizations of our result.

关键词： Girth graphs graph algorithms planar graphs cycles graph separators graph genus shortest paths dynamic algorithms hammock decomposition path and circuit problems

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：