1,721,309 research outputs found
Fully dynamic transitive closure: Breaking through the O(n(2)) barrier
No full textIn this paper we introduce a general framework for casting fully dynamic transitive closure into the problem of reevaluating polynomials over matrices. With this technique, we improve the best known bounds for fully dynamic transitive closure. In particular we devise a deterministic algorithm for general directed graphs that achieves O(n(2)) amortized time for updates, while preserving unit worst-case cost for queries. In case of deletions only, our algorithm performs updates faster in O(n) amortized time. Our matrix-based approach yields an algorithm for directed acyclic graphs which breaks through the O(n(2)) barrier on the single-operation complexity of fully dynamic transitive closure. We can answer queries in O(n(epsilon)) time and perform updates in O(n(omega (1,epsilon ,1)-epsilon) + n(1+epsilon)) time, for any epsilon is an element of [0, 1], where omega (1, epsilon, 1) is the exponent of the multiplication of an nxn(epsilon) matrix by an n(epsilon)xn matrix. The current best bounds on omega (1, epsilon, 1) imply an O(n(0.575)) query time and an O(n(1.575)) update time. Our subquadratic algorithm is randomized, and has one-side error
Engineering shortest path algorithms
Full text linkIn this paper, we report on our own experience in studying a fundamental problem on graphs: all pairs shortest paths. In particular, we discuss the interplay between theory and practice in engineering a simple variant of Dijkstra's shortest path algorithm. In this context, we show that studying heuristics that are efficient in practice can yield interesting clues to the combinatorial properties of the problem, and eventually lead to new theoretically efficient algorithms
Predicting deadlock in store-and-forward networks
No full textAim of this paper is to study the complexity of the Deadlock-Safety problem for Store-and-Forward networks. The following results are shown: 1. the problem is in general NP-complete, even for tree-like networks. It is still NP-complete for various "simple" topologies (including bipartite, grid and two-terminals series-parallel graphs) when each vertex buffer is of unit capacity; 2. the problem is solvable in PTIME for 1-buffer tree-like networks
Hypergraph Traversal Revisited: Cost Measures and Dynamic Algorithms
No full textLecture Notes in Computer Science, Springer Verla
Efficient Splitting and Merging Algorithms for Order Decomposable Problems
No full textLet S be a set whose items are sorted with respect to d ? 1 total orders OE 1 ; : : : ; OE d , and which is subject to dynamic operations, such as insertions of a single item, deletions of a single item, split and concatenate operations performed according to any chosen order OE i (1 i d). This generalizes to dimension d ? 1 the notion of concatenable data structures, such as the 2-3-trees, which support splits and concatenates under a single total order. The main contribution of this paper is a general and novel technique for solving order decomposable problems on S, which yields new and efficient concatenable data structures for dimension d ? 1. By using our technique we maintain S with the following time bounds: O(log n) for the insertion or the deletion of a single item, where n is the number of items currently in S; O(n 1\Gamma1=d ) for splits and concatenates along any order, and for rectangular range queries. The space required is O(n). We provide several applications of ..
- …
