176 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
Accuracy of Author Names in Bibliographic Data Sources: An Italian Case Study
No full textWe investigate the accuracy of how author names are reported in bibliographic records excerpted from four prominent sources: WoS, Scopus, PubMed, and CrossRef. We take as a case study 44,549 publications stored in the internal database of Sapienza University of Rome, one of the largest universities in Europe. While our results indicate generally good accuracy for all bibliographic data sources considered, we highlight a number of issues that undermine the accuracy for certain classes of author names, including compound names and names with diacritics, which are common features to Italian and other Western languages
Fully Dynamic Algorithms for Path Problems on Directed Graphs
No full textIn this thesis we investigate fully dynamic algorithms for path problems on directed graphs. In particular, we focus on two of the most fundamental path problems: fully dynamic transitive closure and fully dynamic single-source shortest paths.
The first part of the thesis presents a new technique which makes it possible to reduce fully dynamic transitive closure to the problem of reevaluating polynomials over matrices when updates of variables are performed. Based on this technique, we devise a new deterministic algorithm which improves the best known bounds for fully dynamic transitive closure. Our algorithm hinges upon the well-known equivalence between transitive closure and matrix multiplication on a closed semiring. We show how to maintain explicitly the transitive closure of a directed graph as a Boolean matrix in O(n^2) amortized time per insertion and deletion of edges. Since an update may change as many as O(n^2) entries of this matrix, this seems to be the best update bound that one could hope for this class of algorithms. We note that maintaining explicitly the transitive closure allows us to answer reachability queries with just one table lookup. We also consider the case where only deletions are allowed and we show how to handle updates faster in O(n) amortized time per operation while maintaining unit lookup per query; in this way we generalize to directed graphs the previous best known deletions-only result for acyclic graphs. Using the same matrix based approach, we also address the problem of maintaining implicitly the transitive closure of a directed graph and we devise the first algorithm which supports both updates and reachability queries in subquadratic time per operation. This result proves that it is actually possible to break through the O(n^2) barrier on the single-operation complexity of fully dynamic transitive closure, and solves a problem that has been open for many years. Our subquadratic algorithm is randomized Monte Carlo and supports update in O(n^1.58) and query in O(n^0.58) worst-case time.
From an experimental point of view, we investigate the practical performances of fully dynamic single-source shortest paths algorithms on directed graphs with arbitrary edge weights. We also propose a variant of the best known algorithms especially designed to be simple and fast in practice while matching the same asymptotic worst-case running time. Our study provides the first experimental evidence of practical dynamic solutions for the problem that are better by several orders of magnitude than recomputing from scratch
Engineering shortest path algorithms
No full textIn 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
Oracles for distances avoiding a link-failure
No full textFor a directed graph G we consider queries of the form: "What is the shortest path distance from vertex x to vertex y in G avoiding a failed link (u, v), and what edge leaving x should we use to get on a such a shortest path?" We show that an oracle for such queries can be stored in 0(n(2) log n) space with a query time of 0(log n). No non-trivial solution was known for this problem
Smooth animation of algorithms in a declarative framework
No full textThanks to the increasing sophistication of modern workstations and display devices, supporting smoothly changing images has nowadays become a valuable feature in software visualization systems, but it seems difficult to achieve in declarative frameworks, as they are basically data (and not event) driven. This paper focuses on the problem of specifying animations of algorithms in a declarative style, addressing both automation and customization issues. We propose a general functional approach to animation modeling where animated behaviors of graphical objects are 'higher-order' attributes of the objects themselves expressed in the form of mathematical functions. These functions provide temporal and spatial information for creating smooth transitions between graphical scenes. The paper also describes the practical embodiment of our mathematical framework in the logic-based software visualization system Leonardo. Differently from previous approaches to smooth algorithm animation, detection of visual events and in-betweening scenes are completely automatic with our technique, Moreover, automation is supported without sacrificing customizability: default animated behaviors of graphical objects are automatically provided by the system, and practical solutions for specifying user-defined animation functions are supported as well. The quality of animations can be therefore incrementally improved by overriding the default behaviors as we show in some examples. (C) 2001 Academic Press
A technique for generating graphical abstractions of program data structures
No full textRepresenting abstract data structures in a real programming language is a key step of algorithm implementation and often requires programmers to introduce language-dependent details irrelevant for both a high-level analysis of the code and algorithm comprehension. In this paper we present a logic-based technique for recovering from the loss of abstraction related to the implementation process in order to create intuitive high-level pictorial representations of data structures, useful for program debugging, research and educational purposes
A portable virtual machine for program debugging and directing
No full textDirectors are reactive systems that monitor the run-time environment and react to the emitted events. Typical examples of directors are debuggers and tools for program analysis and software visualization. In this paper we describe a cross-platform virtual machine that provides advanced facilities for implementing directors with low effort
Combinatorial algorithms for feedback problems in directed graphs
No full textGiven a weighted directed graph G = (V, A), the minimum feedback arc set problem consists of finding a minimum weight set of arcs A' subset of or equal to A such that the directed graph (V, A A') is acyclic. Similarly, the minimum feedback vertex set problem consists of finding a minimum weight set of vertices containing at least one vertex for each directed cycle. Both problems are NP-complete. We present simple combinatorial algorithms for these problems that achieve an approximation ratio bounded by the length, in terms of number of arcs, of a longest simple cycle of the digraph. (C) 2003 Elsevier Science B.V. All rights reserved
Breaking cycles for minimizing crossings
No full textWe consider the one-sided crossing minimization problem (CP): given a bipartite graph G and a permutation x0 of the vertices on a layer, find a permutation x1 of the vertices on the other layer which minimizes the number of edge crossings in any straigthline drawing of G where vertices are placed on two parallel lines and sorted according to x0 and x1. Solving CP represents a fundamental step in the construction of aesthetically pleasing layouts of hierarchies and directed graphs, but unfortunately this problem has been proved to be NP-complete. In this paper we address the strong relation between CP and the problem of computing minimum feedback arc sets in directed graphs and we devise a new approximation algorithm for CP, called PM, that exploits this dependency. We experimentally and visually compare the performance of PM with the performance of well-known algorithms and of recent attractive strategies. Experiments are carried out on different families of randomly generated graphs, on pathological instances, and on real test sets. Performance indicators include both number of edge crossings and running time, as well as structural measures of the problem instances. We found CP to be a very interesting and rich problem from a combinatorial point of view. Our results clearly separate the behavior of the algorithms, proving the effectiveness of PM on most test sets and showing tradeoffs between quality of the solutions and running time. However, if the visual complexity of the drawings is considered, we found no clear winner. This confirms the importance of optimizing also other aesthetic criteria such as symmetry, edge length, and angular resolution
- …
