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

A loop-free shortest-path routing algorithm for dynamic networks

THEORETICAL COMPUTER SCIENCE 2014年 516卷 1-19页

作者： D'Angelo, Gianlorenzo D'Emidio, Mattia Frigioni, Daniele Univ Perugia Dept Math & Informat I-06123 Perugia Italy Univ Laquila Dept Informat Engn Comp Sci & Math I-67100 Laquila Italy

This work introduces Loop-Free Routing (LFR), a new loop-free distance-vector routing algorithm, which is able to update the shortest paths of a distributed network in fully dynamic scenarios. This work also provides an evaluation based on simulations of LFR and Diffuse Update ALgorithm (DUAL), one of the most popular loop-free distance-vector algorithms, which is part of CISCO's widely used Enhanced Interior Gateway Routing Protocol (EIGRP). The simulations are performed on dynamic scenarios based on both real-world and controlled instances. The simulations show that LFR is always the best choice in terms of memory requirements, while in terms of messages sent LFR outperforms DUAL on real-world networks, whereas DUAL is the best choice on controlled scenarios. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Distributed networks Loop-free routing Shortest-path dynamic algorithms

来源：评论

学校读者我要写书评

暂无评论

引用

55th Annual IEEE Symposium on Foundations of Computer Science (FOCS)

作者： Abboud, Amir Williams, Virginia Vassilevska Stanford Univ Dept Comp Sci Palo Alto CA 94304 USA

ISBN: (纸本)9781479965175

We consider several well-studied problems in dynamic algorithms and prove that sufficient progress on any of them would imply a breakthrough on one of five major open problems in the theory of algorithms: 1) Is the 3SUM problem on n numbers in O(n(2-epsilon)) time for some epsilon > 0? 2) Can one determine the satisfiability of a CNF formula on n variables and poly n clauses in O((2 - epsilon)(n) poly n) time for some epsilon > 0? 3) Is the All Pairs Shortest Paths problem for graphs on n vertices in O(n(3-epsilon)) time for some epsilon > 0? 4) Is there a linear time algorithm that detects whether a given graph contains a triangle? 5) Is there an O(n(3-epsilon)) time combinatorial algorithm for nxn Boolean matrix multiplication? The problems we consider include dynamic versions of bipartite perfect matching, bipartite maximum weight matching, single source reachability, single source shortest paths, strong connectivity, subgraph connectivity, diameter approximation and some nongraph problems such as Pagh's problem defined in a recent paper by Patrascu[STOC 2010].

关键词： dynamic algorithms all pairs shortest paths 3SUM lower bounds

来源：评论

学校读者我要写书评

暂无评论

Real-time Traffic Signal Control with dynamic Evolutionary Computation 3

Real-time Traffic Signal Control with Dynamic Evolutionary C...

引用

3rd IIAI International Conference on Advanced Applied Informatics (IIAI-AAI)

作者： Zeng, Kai Gong, Yue-Jiao Zhang, Jun Sun Yat Sen Univ Key Lab Machine Intelligence & Adv Comp Educ Dept Guangdong Prov Dept Comp SciMinist EducKey Lab Software Techno Guangzhou 510275 Guangdong Peoples R China

ISBN: (纸本)9781479941735

Nowadays real-time traffic signal control is a crucial issue with potential benefits in the fields of traffic control, environmental pollution, and energy utilization. In the literature, few related studies have been done with dynamic evolutionary algorithms. In this paper, we proposed a strategy using Collaborative Evolutionary-Swarm Optimization (CESO), which is able to track time-varying optimal solutions effectively. We use the simulator of urban mobility (SUMO), a popular traffic simulator to generate traffic flows. A grid traffic network is designed with several scenarios to simulate changes of traffic flows captured by traffic monitors. We test different traffic changes in the network using the proposed strategy and compare its performance with a traditional evolutionary algorithm. Experimental results show that our algorithm can obtain promising configuration of traffic light cycles and reduce the average delay time of all vehicles in various scenarios.

关键词： dynamic algorithms real-time traffic signal control Collaborative Evolutionary-Swarm Optimization (CESO)

来源：评论

学校读者我要写书评

暂无评论

Doppler frequency estimation-based handover algorithm for long-term evolution networks

引用

IET NETWORKS 2014年第2期3卷 88-96页

作者： Altrad, Omar Muhaidat, Sami Yoo, Paul D. Simon Fraser Univ Burnaby BC Canada Khalifa Univ Abu Dhabi U Arab Emirates Univ Surrey CCSR Guildford Surrey England

Mobile cellular radio systems have become complex multi-layered systems with a mixed architecture of macro and micro cells;therefore, a dynamic method of triggering the handover algorithm in such systems is invaluable and required. In this paper the authors develop a simple handover mechanism to adapt for a fast moving mobile station requesting a handover, in which the authors utilise a Doppler frequency estimation in the downlink for adjustment and apply it to a long-term evolution (LTE) network. This method is beneficial for high speed mobiles in macro and/or micro cells, in which for the latter the cell radius is small and needs a dynamic algorithm to respond in a timely manner. The main objective of this study is to investigate the performance of the proposed algorithm;hence, a system layout is specifically designed for this study. Other factors, such as interference, which may affect the performance of the suggested system are not addressed here. The main concern is to study and compare the proposed algorithm to the standard handover algorithm currently implemented in LTE. Simulations at the system level show a marked decrease in the average number of handovers requested.

关键词： Frequency estimation Microcells Local thermodynamic equilibrium macro commands algorithms system level Handover dynamic algorithms Doppler frequency Long Term Evolution

来源：评论

学校读者我要写书评

暂无评论

Simple Deterministic algorithms for Fully dynamic Maximal Matching 13

Simple Deterministic Algorithms for Fully Dynamic Maximal Ma...

引用

45th Annual ACM Symposium on the Theory of Computing (STOC)

作者： Neiman, Ofer Solomon, Shay Ben Gurion Univ Negev POB 653 IL-84105 Beer Sheva Israel Weizmann Inst Sci IL-76100 Rehovot Israel

ISBN: (纸本)9781450320290

A maximal matching can be maintained in fully dynamic (supporting both addition and deletion of edges) n-vertex graphs using a trivial deterministic algorithm with a worst case update time of 0(n). No deterministic algorithm that outperforms the na ve 0(n) one was reported up to this date. The only progress in this direction is due to Ivkovie and Lloyd [14], who in 1993 devised a deterministic algorithm with an amortized update time of 0((n+m) / 2), where m is the number of edges. In this paper we show the first deterministic fully dynamic algorithm that outperforms the trivial one. Specifically, we provide a deterministic worst-case update time of O(N',1/7). Moreover, our algorithm maintains a matching which is in fact a 3/2 -approximate maximum cardinality matching (MCM). We remark that no fully dynamic algorithm for maintaining (2 0 -approximate MCM improving upon the na ve 0(n) was known prior to this work, even allowing amortized time bounds and randomization. For low arboricity graphs (e.g., planar graphs and graphs excluding fixed minors), we devise another simple deterministic algorithm with sub -logarithmic update time. Specifically, it maintains a fully dynamic maximal matching with amortized update time of 0 (log n/ log log n). This result addresses an open question of Onak and Rubinfeld [19]. We also show a deterministic algorithm with optimal space usage of 0(n + m), that for arbitrary graphs maintains a maximal matching with amortized update time of OHI/n,).

关键词： dynamic algorithms maximal matching maximum matching

来源：评论

学校读者我要写书评

暂无评论

dynamic Structural Analysis for DAEs 14

Dynamic Structural Analysis for DAEs

引用

Simulation Multiconference

作者： Christoph Hoger Department of Software Engineering and Theoretical Computer Science Technische Universitat Berlin

ISBN: (纸本)9781632667335

Efficient simulation of higher-index variable-structure DAE requires index-reduction during simulation. Hence, the performance of the implemented index-reduction method is crucial. When the same algorithm has to be calculated for slightly different inputs, dynamic algorithms can outperform their static counterparts by reusing common elements of the solutions. We present the dynamic Σ-method, a correct and efficient index-reduction method for dynamic systems. The dynamic Σ-method provides large performance gains for large, homogeneous models.

关键词： DAE Index Reduction Hybrid System Structural Variability hybrid systems dynamic structural analysis REDUCTION METHODS dynamic algorithms dynamic systems

来源：评论

学校读者我要写书评

暂无评论

Engineering a New Algorithm for Distributed Shortest Paths on dynamic Networks

引用

ALGORITHMICA 2013年第1期66卷 51-86页

作者： Cicerone, Serafino D'Angelo, Gianlorenzo Di Stefano, Gabriele Frigioni, Daniele Maurizio, Vinicio Univ Aquila Dept Elect & Informat Engn I-67100 Laquila Italy MASCOTTE Project I3S CNRS UNSA INRIA F-06902 Sophia Antipolis France

We study the problem of dynamically updating all-pairs shortest paths in a distributed network while edge update operations occur to the network. We consider the practical case of a dynamic network in which an edge update can occur while one or more other edge updates are under processing. A node of the network might be affected by a subset of these changes, thus being involved in the concurrent executions related to such changes. In this paper, we provide a new algorithm for this problem, and experimentally compare its performance with respect to those of the most popular solutions in the literature: the classical distributed Bellman-Ford method, which is still used in real network and implemented in the RIP protocol, and DUAL, the Diffuse Update ALgorithm, which is part of CISCO's widely used EIGRP protocol. As input to the algorithms, we used both real-world and artificial instances of the problem. The experiments performed show that the space occupancy per node required by the new algorithm is smaller than that required by both Bellman-Ford and DUAL. In terms of messages, the new algorithm outperforms both Bellman-Ford and DUAL on the real-world topologies, while on artificial instances, the new algorithm sends a number of messages that is more than that of DUAL and much smaller than that of Bellman-Ford.

关键词： Shortest paths Distributed networks dynamic algorithms Concurrent update Experimental analysis

来源：评论

学校读者我要写书评

暂无评论

Based on MG-OXC Routing and Multi-Granularity Assignment Algorithm

Based on MG-OXC Routing and Multi-Granularity Assignment Alg...

引用

Cross Strait Quad-Regional Radio Science and Wireless Technology Conference (CSQRWC)

作者： Wang Jianzhong Zhang Ping Sichuan Normal Univ Coll Fundamental Educ Chengdu 610068 Peoples R China

ISBN: (纸本)9781479921256

In this paper we focuses on the optimal design of Multi-Granularity optical Cross-connect (MG-OXC) node based on three stage (fiber, waveband, and wavelength) multiplexing scheme and dynamic algorithm (including routing and multiGranularity assignment algorithm) for Multi-Granularity Optical Networks (MG-ON), under dynamic traffic conditions. The proposed MG-OXC routing and assignment algorithm can reduce both the number of used ports and the cost of an existing network. The performance of our MG-ON scenario is evaluated with numerical experiments under NSFNET topology and comparisons are made with OXC-based wavelength routed optical networks. The results show that the performance of MGON is close to WRON with proper design.

关键词： Allocation Algorithm Network routing dynamic algorithms Fiber optic networks harbors Optimal design Wavelength multiplexing Wavelength routing Optical Cross-Connect

来源：评论

学校读者我要写书评

暂无评论

Recursive algorithms for phylogenetic tree counting

引用

algorithms FOR MOLECULAR BIOLOGY 2013年第1期8卷 26-26页

作者： Gavryushkina, Alexandra Welch, David Drummond, Alexei J. Univ Auckland Dept Comp Sci Auckland 1 New Zealand Univ Auckland Allan Wilson Ctr Mol Ecol & Evolut Auckland 1 New Zealand

Background: In Bayesian phylogenetic inference we are interested in distributions over a space of trees. The number of trees in a tree space is an important characteristic of the space and is useful for specifying prior distributions. When all samples come from the same time point and no prior information available on divergence times, the tree counting problem is easy. However, when fossil evidence is used in the inference to constrain the tree or data are sampled serially, new tree spaces arise and counting the number of trees is more difficult. Results: We describe an algorithm that is polynomial in the number of sampled individuals for counting of resolutions of a constraint tree assuming that the number of constraints is fixed. We generalise this algorithm to counting resolutions of a fully ranked constraint tree. We describe a quadratic algorithm for counting the number of possible fully ranked trees on n sampled individuals. We introduce a new type of tree, called a fully ranked tree with sampled ancestors, and describe a cubic time algorithm for counting the number of such trees on n sampled individuals. Conclusions: These algorithms should be employed for Bayesian Markov chain Monte Carlo inference when fossil data are included or data are serially sampled.

关键词： Ranked tree Constraint tree Resolution Counting trees dynamic algorithms Bayesian tree prior Phylogenetics

来源：评论

学校读者我要写书评

暂无评论

dynamic APPROXIMATE ALL-PAIRS SHORTEST PATHS IN UNDIRECTED GRAPHS

引用

SIAM JOURNAL ON COMPUTING 2012年第3期41卷 670-683页

作者： 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 three new dynamic algorithms for the approximate all-pairs shortest paths problem in unweighted undirected graphs: (i) For any fixed epsilon > 0, a decremental algorithm with an expected total running time of (O) over tilde (mn), where m is the number of edges and n is the number of vertices in the initial graph. Each distance query is answered in O(1) worst-case time, and the stretch of the returned distances is at most 1 + epsilon. The algorithm uses (O) over tilde (n(2)) space. (ii) For any fixed integer k >= 1, a decremental algorithm with an expected total running time of (O) over tilde (mn). Each query is answered in O(1) worst-case time, and the stretch of the returned distances is at most 2k - 1. This algorithm, however, uses only O(m + n(1+1/k)) space. It is obtained by dynamizing techniques of Thorup and Zwick. In addition to being more space efficient, this algorithm is also one of the building blocks used to obtain the first algorithm. (iii) For any fixed epsilon, delta > 0 and every t <= m(1/2-delta), a fully dynamic algorithm with an expected amortized update time of (O) over tilde (mn/t) and worst-case query time of O(t). The stretch of the returned distances is at most 1 + epsilon. All algorithms can also be made to work on undirected graphs with small integer edge weights. If the largest edge weight is b, then all bounds on the running times are multiplied by b.

关键词： dynamic algorithms transitive closure strongly connected components

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：