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

An O(n^2.75) Algorithm for Incremental Topological Ordering

ACM TRANSACTIONS ON algorithms 2008年第4期4卷 1–14页

作者： Ajwani, Deepak Friedrich, Tobias Meyer, Ulrich Max Planck Inst Informat D-66123 Saarbrucken Germany Goethe Univ Frankfurt Inst Comp Sci D-60325 Frankfurt Germany

We present a simple algorithm which maintains the topological order of a directed acyclic graph (DAG) with n nodes, under an online edge insertion sequence, in O(n(2.75)) time, independent of the number m of edges inserted. For dense DAGs, this is an improvement over the previous best result of O(min{m(3/2) log n, m (3/2) + n(2) log n}) by Katriel and Bodlaender [2006]. We also provide an empirical comparison of our algorithm with other algorithms for incremental topological sorting.

关键词： dynamic algorithms graphs online algorithms topological order

来源：评论

学校读者我要写书评

暂无评论

Two methods for the generation of chordal graphs

引用

ANNALS OF OPERATIONS RESEARCH 2008年第1期157卷 47-60页

作者： Markenzon, Lilian Vernet, Oswaldo Araujo, Luiz Henrique Univ Fed Rio de Janeiro Nucl Comp Elect Rio De Janeiro Brazil Inst Militar Engn Rio De Janeiro Brazil

In this paper two methods for automatic generation of connected chordal graphs are proposed: the first one is based on new results concerning the dynamic maintenance of chordality under edge insertions;the second is based on expansion/merging of maximal cliques. Theoretical and experimental results are presented. In both methods, chordality is preserved along the whole generation process.

关键词： chordal graphs dynamic algorithms clique-tree graph generation

来源：评论

学校读者我要写书评

暂无评论

Memory Management for Self-Adjusting Computation 08

Memory Management for Self-Adjusting Computation

引用

International Symposium on Memory Management

作者： Hammer, Matthew A. Acar, Umut A. Toyota Technol Inst Chicago IL USA

ISBN: (纸本)9781605581347

The cost of reclaiming,pace with traversal-based garbage collection is inversely proportional to the amount of free memory, i.e., O(1 /(1 - f)), where f is the fraction of memory that is live. Consequently, the cost of garbage collection can be very high when the size of the live data remains large relative to the available free space. Intuitively, this is because allocating it small amount of memory,pace will require the garbage collector to traverse a fraction of the memory only to discover little garbage. This is unfortunate because in some application domains the size of the memory-resident data can be generally high. This can cause high GC overheads, especially when generational assumptions do not hold. One Such application domain is self-adjusting computation, where computations use memory-resident execution traces ill order to respond to changes to their state (e.g., inputs) efficiently. This paper proposes memory-management techniques for self-adjusting computation that remain efficient even when the size of the live data is large. More precisely, the proposed techniques guarantee O(1) amortized cost for each reclaimed memory object. We propose it set of primitives for self-adjusting computation that support the proposed memory management techniques. The primitives provide in operation for allocating memory: we reclaim unused memory automatically. We implement it library for supporting the primitives in the C language and perform an experimental evaluation. Our experiments show that the approach can be implemented with reasonably small constant-factor overheads and that the programs written using the library behave optimally. Compared to previous implementations, We measure up to all order of magnitude improvement in performance and up to it 75% reduction in space usage.

关键词： Self-adjusting computation memory management garbage collection memoization dynamic dependence graphs dynamic algorithms computational geometry performance

来源：评论

学校读者我要写书评

暂无评论

Performance comparison of algorithms for the dynamic shortest path problem

Performance comparison of algorithms for the dynamic shortes...

引用

19th Workshop on Circuits and Systems

作者： Taoka, Satoshi Takafuji, Daisuke Iguchi, Takashi Watanabe, Toshimasa Hiroshima Univ Grad Sch Engn Higashihiroshima 7398527 Japan

An edge-weighted directed graph is referred to as a network in this paper, and an edge operation is an operation that increases or decreases an edge weight. Decreasing an edge weight from the infinite to a finite value or increasing any edge weight from a finite one to the infinite corresponds to addition or deletion of this edge, respectively. The dynamic shortest path problem (DSPP for short) is defined by "Given any network with a specified vertex (denoted as s), and any sequence of edge operations, construct a shortest path tree of each network obtained by executing those edge operations one by one in the order of the sequence." As an application, fast routing for an interior network using link state protocols, such as OSPF and IS-IS, requires solving DSPP efficiently. In this paper, among as many existing algorithms as possible, including those which execute several edge operations simultaneously, fundamental and/or important algorithms are implemented and their capability is evaluated based on the results of computational experiments.

关键词： networks shortest paths dynamic algorithms static algorithms computational experiments

来源：评论

学校读者我要写书评

暂无评论

Distributed Approximate Matching

Distributed Approximate Matching

引用

16th Annual ACM Symposium on Principles of Distributed Computing

作者： Lotker, Zvi Patt-Shamir, Boaz Rosen, Adi Ben Gurion Univ Negev Dept Commun Syst Engn IL-84105 Beer Sheva Israel

ISBN: (纸本)9781595936165

We consider distributed algorithms for approximate maximum matching on general graphs. Our main result is a randomized (4 + epsilon)-approximation distributed algorithm for weighted maximum matching;whose running time is O(log n) for any constant epsilon > 0, where n is the number of nodes in the graph. In addition, we consider the dynamic case, where nodes are inserted and deleted one at a time. For unweighted dynamic graphs, we give an algorithm that maintains a (1 + epsilon)-approximation in O(1/epsilon) time for each node insertion or deletion. For weighted dynamic graphs we give a constant-factor approximation algorithm that runs in constant time for each insertion or deletion.

关键词： Graph algorithms distributed algorithms maximum matching dynamic algorithms distributed approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

An algorithm for fast composition of weighted finite-state transducers

An algorithm for fast composition of weighted finite-state t...

引用

IEEE Workshop on Automatic Speech Recognition and Understanding

作者： McDonough, John Stoimenov, Emilian Klakow, Dietrich Univ Saarland D-6600 Saarbrucken Germany Univ Karlsruhe Inst Theoret Comp Sci Karlsruhe Germany Univ Karlsruhe Inst Intelligent Sensor Actuator Syst Karlsruhe Germany

ISBN: (纸本)9781424417452

In automatic speech recognition based on weighted-finite transducers, a static decoding graph HC circle L circle G is typically constructed. In this work, we first show how the size of the decoding graph can be reduced and the necessity of determining it can be eliminated by removing the ambiguity associated with transitions to the backoff state or states in G. We then show how the static construction can be avoided entirely by performing fast on-the-fly composition of HC and L circle G. We demonstrate that speech recognition based on this on-the-fly composition approximately 80% more run-time than recognition based on the statically-expanded network R, which makes it competitive compared with other dynamic expansion algorithms that have appeared in the literature. Moreover, the dynamic algorithm requires a factor of approximately seven less main memory as the recognition based on the static decoding graph.

关键词： Transducers DECODING Fasting algorithms dynamic algorithms

来源：评论

学校读者我要写书评

暂无评论

Fully dynamic recognition algorithm and certificate for directed cographs

引用

DISCRETE APPLIED MATHEMATICS 2006年第12期154卷 1722-1741页

作者： Crespelle, C. Paul, C. LIRMM CNRS Dept Informat Montpellier France

This paper presents an optimal fully dynamic recognition algorithm for directed cographs. Given the modular decomposition tree of a directed cograph G, the algorithm supports arc and vertex modification (insertion or deletion) in O(d) time where d is the number of arcs involved in the operation. Moreover, if the modified graph remains a directed cograph, the modular decomposition tree is updated;otherwise, a certificate is returned within the same complexity. (c) 2006 Elsevier B.V. All rights reserved.

关键词： dynamic algorithms directed cographs certifying algorithms

来源：评论

学校读者我要写书评

暂无评论

Adaptive functional programming

引用

ACM TRANSACTIONS ON PROGRAMMING LANGUAGES AND SYSTEMS 2006年第6期28卷 990-1034页

作者： Acar, Umut A. Blelloch, Guy E. Harper, Robert Toyota Technol Inst Chicago IL USA Carnegie Mellon Univ Pittsburgh PA USA

We present techniques for incremental computing by introducing adaptive functional programming. As an adaptive program executes, the underlying system represents the data and control dependences in the execution in the form of a dynamic dependence graph. When the input to the program changes, a change propagation algorithm updates the output and the dynamic dependence graph by propagating changes through the graph and re-executing code where necessary. Adaptive programs adapt their output to any change in the input, small or large. We show that adaptivity techniques are practical by giving an efficient implementation as a small ML library. The library consists of three operations for making a program adaptive, plus two operations for making changes to the input and adapting the output to these changes. We give a general bound on the time it takes to adapt the output, and based on this, show that an adaptive Quicksort adapts its output in logarithmic time when its input is extended by one key. To show the safety and correctness of the mechanism we give a formal definition of AFL, a call-by-value functional language extended with adaptivity primitives. The modal type system of AFL enforces correct usage of the adaptivity mechanism, which can only be checked at run time in the ML library. Based on the AFL dynamic semantics, we formalize the change-propagation algorithm and prove its correctness. Categories and Subject Descriptors: D.1.0 [Programming Techniques]: General;D.1.1 [Programming Techniques]: Applicative (Functional) Programming;D.3.0 [Programming Languages]: General;D.3.1 [Programming Languages]: Formal Definitions and Theory;F.2.0 [Analysis of algorithms and Problem Complexity]: General;F.3.2 [Logics and Meanings of Programs]: Semantics of Programming Languages.

关键词： algorithms languages performance theory incremental computation adaptive computation dynamic algorithms

来源：评论

学校读者我要写书评

暂无评论

Online Topological Ordering

引用

ACM TRANSACTIONS ON algorithms 2006年第3期2卷 364-379页

作者： Katriel, Irit Bodlaender, Hans L. Univ Aarhus BRICS Aarhus Denmark Univ Utrecht Inst Informat & Comp Sci Utrecht Netherlands

It is shown that the problem of maintaining the topological order of the nodes of a directed acyclic graph while inserting m edges can be solved in O (min{m(3/2) log n, m(3/2) + n(2) log n}) time, an improvement over the best known result of O(mn). In addition, we analyze the complexity of the same algorithm with respect to the treewidth k of the underlying undirected graph. We show that the algorithm runs in time O (mk log(2) n) for general k and that it can be implemented to run in O (n log n) time on trees, which is optimal. The algorithm also detects cycles in the input.

关键词： dynamic algorithms graphs online algorithms topological order treewidth

来源：评论

学校读者我要写书评

暂无评论

Self-Adapting Scheduling for tasks with dependencies in stochastic environments

Self-Adapting Scheduling for tasks with dependencies in stoc...

引用

IEEE International Conference on Cluster Computing

作者： Riakotakis, I. Ciorba, F. M. Andronikos, T. Papakonstantinou, G. Natl Tech Univ Athens Dept Elect & Comp Engn Comp Syst Lab Zografou Campus GR-15773 Athens Greece

ISBN: (纸本)9781424403271

This paper addresses dynamic load balancing algorithms for non-dedicated heterogeneous clusters of workstations. We propose an algorithm called Self-Adapting Scheduling (SAS), targeted at nested loops with dependencies in a stochastic environment. This means that the load entering the system, not belonging to the parallel application under execution. follows an unpredictable pattern which can be modeled by a stochastic process. SAS takes into account the history of previous timing results and the load patterns in order to make accurate load balancing predictions. We studs, the performance of SAS in comparison with DTSS. We established in previous work that DTSS is the most efficient self-scheduling algorithm for loops with dependencies on heterogeneous clusters. We test our algorithm under the assumption that the interarrival times and life-times of incoming jobs are exponentially-distributed. The experimental results show that SAS significantly outper-forms DTSS especially with rapidly varying loads.

关键词： dynamic algorithms load balancing loops with dependencies stochastic environments

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：