1,626 research outputs found
Experimental Analysis of Dynamic All Pairs Shortest Path Algorithms
No full textWe present the results of an extensive computational study on dynamic algorithms for all pairs shortest path problems. We describe our implementations of the recent dynamic algorithms of King [1999] and of Demetrescu and Italiano [2006], and compare them to the dynamic algorithm of Ramalingam and Reps and to static algorithms on random, real-world and hard instances. Our experimental data suggest that some of the dynamic algorithms and their algorithmic techniques can be really of practical value in many situations
Dynamic shortest paths and transitive closure: algorithmic techniques and data structures
No full textIn this paper, we survey fully dynamic algorithms for path problems on general directed graphs. In particular, we consider two fundamental problems: dynamic transitive closure and dynamic shortest paths. Although research on these problems spans over more than three decades, in the last couple of years many novel algorithmic techniques have been proposed. In this survey, we will make a special effort to abstract some combinatorial and algebraic properties, and some common data-structural tools that are at the base of those techniques. This will help us try to present some of the newest results in a unifying framework so that they can be better understood and deployed also by non-specialists. © 2005 Elsevier B.V. All rights reserved
Mantaining dynamic matrices for fully dynamic transitive closure
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. We observe that fully dynamic transitive closure algorithms with O(1) query time maintain explicitly the transitive closure of the input graph, in order to answer each query with exactly one lookup (on its adjacency matrix). Since an update may change as many as Omega(n(2)) entries of this matrix, no better bounds are possible for this class of algorithms
Sorting and searching in faulty memories
No full textIn this paper we investigate the design and analysis of algorithms resilient to memory faults. We focus on algorithms that, despite the corruption of some memory values during their execution, are nevertheless able to produce a correct output at least on the set of uncorrupted values. In this framework, we consider two fundamental problems: sorting and searching. In particular, we prove that any O(nlog∈n) comparison-based sorting algorithm can tolerate the corruption of at most O((nlog∈n) 1/2) keys. Furthermore, we present one comparison-based sorting algorithm with optimal space and running time that is resilient to O((nlog∈n) 1/3) memory faults. We also prove polylogarithmic lower and upper bounds on resilient searching. © 2007 Springer Science+Business Media, LLC
Algorithmic techniques for maintaining shortest routes in dynamic networks
No full textIn this paper, we survey algorithms for shortest paths in dynamic networks. Although research on this problem spans over more than three decades, in the last couple of years many novel algorithmic techniques have been proposed. In this survey, we will make a special effort to abstract some combinatorial and algebraic properties, and some common data-structural tools that are at the base of those techniques. This will help us try to present some of the newest results in a unifying framework so that they can be better understood and deployed also by non-specialists. © 2007 Elsevier B.V. All rights reserved
The Quest for the shortest route
No full textTo examine, analyze, and manipulate a problem to the point of designing an algorithm for solving it is an exercise of fundamental value in many fields. With so many everyday activities governed by algorithmic principles, the power, precision, reliability and speed of execution demanded by users have transformed the design and construction of algorithms from a creative, artisanal activity into a full-fledged science in its own right. This book is aimed at all those who exploit the results of this new science, as designers and as consumers. The first chapter is an overview of the related history, demonstrating the long development of ideas such as recursion and more recent formalizations such as computability. The second chapter shows how the design of algorithms requires appropriate techniques and sophisticated organization of data. In the subsequent chapters the contributing authors present examples from diverse areas - such as routing and networking problems, Web search, information security, auctions and games, complexity and randomness, and the life sciences - that show how algorithmic thinking offers practical solutions and also deepens domain knowledge. The contributing authors are top-class researchers with considerable academic and industrial experience; they are also excellent educators and communicators and they draw on this experience with enthusiasm and humor. This book is an excellent introduction to an intriguing domain and it will be enjoyed by undergraduate and postgraduate students in computer science, engineering, and mathematics, and more broadly by all those engaged with algorithmic thinking
Finding strong articulation points and strong bridges in linear time
No full textGiven a directed graph G, an edge is a strong bridge if its removal increases the number of strongly connected components of G. Similarly, we say that a vertex is a strong articulation point if its removal increases the number of strongly connected components of G. In this paper, we present linear-time algorithms for computing all the strong bridges and all the strong articulation points of directed graphs, solving an open problem posed in Beldiceanu et al. (2005)
CHECKCOL: improved local search for graph coloring
No full textIn this paper we present a novel coloring algorithm based on local search. We analyze its performance, and report several experimental results on DIMACS benchmark graphs. From our experiments, this algorithm looks robust, and yields a substantial speed up on previous algorithms for coloring. Our algorithm improves the best known coloring for four different DIMACS benchmark graphs: namely, Le450-25c, Le450-25d and Flat300_28_0 and Flat1000_76_0. Furthermore, we have run experiments on a simulator to get insights on its cache consciousness: from these experiments, it appears that the algorithm performs substantially less cache misses than other existing algorithms. © 2005 Elsevier B.V. All rights reserved
- …
